记录编号	402217	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015] 幻想乡战略游戏	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	6.829 s
提交时间	2017-05-05 14:28:21	内存使用	29.49 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct edge{int f,t,l;}w[N];
int n,Q,head[N],next[N];
void add(int f,int t,int l){
	static int cnt=0;
	w[++cnt]=(edge){f,t,l};
	next[cnt]=head[f];
	head[f]=cnt;
}
int dis[N][20],dep[N];
int tree_size,root,big[N],size[N],h[N],fa[N];
bool vis[N];
void getroot(int x,int fa){
	size[x]=1;big[x]=0;
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]||v==fa) continue;
		getroot(v,x);
		size[x]+=size[v];
		big[x]=max(big[x],size[v]);
	}
	if (size[x]>=tree_size/2&&big[x]<=tree_size/2) root=x;
}
void geth(int x,int fa){
	size[x]=1;
	dis[x][++h[x]]=dep[x];
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]||v==fa) continue;
		dep[v]=dep[x]+w[i].l;
		geth(v,x);
		size[x]+=size[v];
	}
}
typedef pair<int,int> pr;
vector<pr> E[N];
void build(int x){
	vis[x]=1;dep[x]=0;geth(x,0);
	for (int i=head[x];i;i=next[i]){
		int v=w[i].t;
		if (vis[v]) continue;
		tree_size=size[v];
		getroot(v,0);
		fa[root]=x;
		E[x].push_back(pr(v,root));
		build(root);
	}
}
int cnt[N];ll up[N],sum[N];
//cnt[x]表示分治树x中军队总个数
//sum[x]表示分治树中x子树到根带权距离和
//up[x]表示子树x对sum[fa[x]]的贡献
void add(int p,int d){//给p的权增加d
	for (int x=p;x;x=fa[x]){
		cnt[x]+=d;
		sum[x]+=(ll)dis[p][h[x]]*d;
		up[x]+=(ll)dis[p][h[x]-1]*d;
	}
}
ll query(int p){//返回重心设在p的权值
	ll ans=sum[p];
	for (int x=p;fa[x];x=fa[x])
		ans+=sum[fa[x]]-up[x]+ll(cnt[fa[x]]-cnt[x])*dis[p][h[x]-1];
	return ans;
}
ll solve(int x){
	ll ans=query(x);
	for (int i=E[x].size()-1;i>=0;i--){
		ll val=query(E[x][i].first);
		if (val<ans) return solve(E[x][i].second);
	}
	return ans;
}

int main()
{
	freopen("zjoi15_tree.in","r",stdin);
	freopen("zjoi15_tree.out","w",stdout);
	scanf("%d%d",&n,&Q);
	for (int i=1;i<n;i++){
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		add(u,v,l);add(v,u,l);
	}
	tree_size=n;
	getroot(1,0);
	int Root=root;
	build(root);
	while (Q--){
		int x,e;
		scanf("%d%d",&x,&e);
		add(x,e);
		printf("%lld\n",solve(Root));
	}
	return 0;
}