记录编号	159736	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015] 幻想乡战略游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	25.349 s
提交时间	2015-04-22 16:11:36	内存使用	26.07 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int SIZEN=100010;
//重要全局变量:
int N,Q;
vector<pair<int,int> > c[SIZEN];
int DC_root;
vector<pair<int,int> > DC_son[SIZEN];//first是重心,second是连向边
int DC_father[SIZEN];


//读入组件:
void add_edge(int a,int b,int w){
	c[a].push_back(make_pair(b,w));
}
void read(void){
	scanf("%d%d",&N,&Q);
	int a,b,c;
	for(int i=1;i<N;i++){
		scanf("%d%d%d",&a,&b,&c);
		add_edge(a,b,c);
		add_edge(b,a,c);
	}
}


//距离运算组件:
int depth[SIZEN]={0};
int DFS_lis[SIZEN*2],DFS_len=0;
int dfn[SIZEN]={0};
bool vis[SIZEN]={0};
void DFS(int x){
	DFS_len++;
	dfn[x]=DFS_len;
	DFS_lis[DFS_len]=x;
	vis[x]=true;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i].first;
		if(vis[u]) continue;
		depth[u]=depth[x]+c[x][i].second;
		DFS(u);
		DFS_lis[++DFS_len]=x;
	}
}
int ST[SIZEN*2][20]={0};
int log_2[SIZEN*2]={0};
int get_log(int n){
	int ans=-1;
	while(n) ans++,n>>=1;
	return ans;
}
int get_shallower(int x,int y){
	return depth[x]<depth[y]?x:y;
}
void ST_prepare(void){
	for(int i=1;i<=DFS_len;i++) log_2[i]=get_log(i);
	for(int i=1;i<=DFS_len;i++) ST[i][0]=DFS_lis[i];
	for(int j=1;j<=log_2[DFS_len];j++){
		for(int i=1;i<=DFS_len;i++){
			if(i+(1<<j)-1<=DFS_len){
				ST[i][j]=get_shallower(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
			}
		}
	}
}
void prepare_dist(void){
	DFS(1);
	ST_prepare();
}
int get_dist(int a,int b){
	int l=dfn[a],r=dfn[b];
	if(l>r) swap(l,r);
	int m=log_2[r-l+1];
	int g=get_shallower(ST[l][m],ST[r-(1<<m)+1][m]);
	return depth[a]+depth[b]-2*depth[g];
}


//分治结构组件:
bool DC_decided[SIZEN]={0};
int sub_size[SIZEN]={0};//子树大小
int mx_sub[SIZEN]={0};//分裂以后的最大块
int now_root;
void DC_calc_size(int x,int fa){
	sub_size[x]=1;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i].first;
		if(DC_decided[u]||u==fa) continue;
		DC_calc_size(u,x);
		sub_size[x]+=sub_size[u];
	}
}
void DC_select_root(int x,int upcnt,int fa){
	mx_sub[x]=upcnt;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i].first;
		if(DC_decided[u]||u==fa) continue;
		mx_sub[x]=max(mx_sub[x],sub_size[u]);
		DC_select_root(u,upcnt+sub_size[x]-sub_size[u],x);
	}
	if(now_root==-1||mx_sub[x]<mx_sub[now_root]) now_root=x;
}
int DC_DFS(int x){//搞出x所在连通块内的根
	DC_calc_size(x,0);
	now_root=-1;
	DC_select_root(x,0,0);
	int rt=now_root;
	DC_decided[rt]=true;
	for(int i=0;i<c[rt].size();i++){
		int u=c[rt][i].first;
		if(DC_decided[u]) continue;
		int v=DC_DFS(u);
		DC_son[rt].push_back(make_pair(v,u));
		DC_father[v]=rt;
	}
	return rt;
}


//修改和查询组件:
LL sub_cost[SIZEN];//给本层连通块补给的代价
LL sub_sum[SIZEN];//本层连通块的大小
LL up_ctb[SIZEN];//这一连通块对上一层重心补给代价的贡献
void modify(int x,LL w){//x节点的军队数+=w
	int rt=x;
	while(rt){
		sub_cost[rt]+=get_dist(rt,x)*w;//对rt的贡献
		sub_sum[rt]+=w;
		if(rt!=DC_root) up_ctb[rt]+=get_dist(DC_father[rt],x)*w;//对rt的上级重心的贡献
		rt=DC_father[rt];
	}
}
LL all_cost[SIZEN];//辅助数组,意为给全部节点补给的代价
LL unsel_cost[SIZEN],unsel_sum[SIZEN];
void walk_down(int x,int u){//从重心x走向次级重心u
	unsel_cost[x]=sub_cost[x]-up_ctb[u];
	unsel_sum[x]=sub_sum[x]-sub_sum[u];
	all_cost[u]=sub_cost[u];
	int rt=x;
	while(rt){
		all_cost[u]+=unsel_cost[rt]+unsel_sum[rt]*get_dist(rt,u);
		rt=DC_father[rt];
	}
}
LL calc_real_son(int x,int v,int u){//计算v的代价,其中v是x的树儿子,所在重心是u
	unsel_cost[x]=sub_cost[x]-up_ctb[u];
	unsel_sum[x]=sub_sum[x]-sub_sum[u];
	LL ans=0;
	int rt=x;
	while(rt){
		ans+=unsel_cost[rt]+unsel_sum[rt]*get_dist(rt,v);
		rt=DC_father[rt];
	}
	ans+=up_ctb[u]-sub_sum[u]*get_dist(x,v);
	return ans;
}
LL query(int x){//在x子树中寻找答案,此时all_cost[x]已经求出
	LL ans=all_cost[x];
	int id=-1;
	for(int i=0;i<DC_son[x].size();i++){
		int rt=DC_son[x][i].first,u=DC_son[x][i].second;
		all_cost[u]=calc_real_son(x,u,rt);
		if(all_cost[u]<ans){
			ans=all_cost[u];
			id=rt;
		}
	}
	if(id!=-1){
		walk_down(x,id);
		ans=query(id);
	}
	return ans;
}
LL query(void){
	all_cost[DC_root]=sub_cost[DC_root];
	return query(DC_root);
}


int main(){
	freopen("zjoi15_tree.in","r",stdin);
	freopen("zjoi15_tree.out","w",stdout);
	read();//读入
	prepare_dist();//加载距离运算套装
	DC_root=DC_DFS(1);//建立分治结构
	int a,w;
	for(int i=1;i<=Q;i++){
		scanf("%d%d",&a,&w);
		modify(a,w);
		printf("%lld\n",query());
	}
	return 0;
}