记录编号	594721	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015] 幻想乡战略游戏	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	6.965 s
提交时间	2024-10-04 18:02:56	内存使用	28.26 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100010 
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node{
	ll sum,maxz,tag,max_id;
	ll l,r,sum_len;
}tr[MAXN*4];
ll n,q,idx,cnt,S,sum_siz;
ll dep[MAXN],siz[MAXN],son[MAXN],f[MAXN],len[MAXN],dep_len[MAXN];
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2],val[MAXN*2];
ll tp[MAXN],id[MAXN],re_id[MAXN];
void build(ll x,ll y,ll w){
	nxt[++idx]=hd[x];
	ed[idx]=y;
	hd[x]=idx;
	val[idx]=w;
}
void dfs1(ll now,ll fa){
	dep[now]=dep[fa]+1,siz[now]=1,f[now]=fa;
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		if(y==fa)continue;
		dep_len[y]=dep_len[now]+val[i];
		len[y]=val[i];
		dfs1(y,now);
		siz[now]+=siz[y];
		if(siz[y]>siz[son[now]])son[now]=y;
	}
}
void dfs2(ll now,ll fnt){
	tp[now]=fnt;
	id[now]=++cnt;
	re_id[cnt]=now;
	if(!son[now])return;
	dfs2(son[now],fnt);
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		if(y==f[now]||y==son[now])continue;
		dfs2(y,y);
	}
}
void push_up(ll now){
	if(tr[now*2].maxz>tr[now*2+1].maxz){
		tr[now].maxz=tr[now*2].maxz;
		tr[now].max_id=tr[now*2].max_id;
	}else{
		tr[now].maxz=tr[now*2+1].maxz;
		tr[now].max_id=tr[now*2+1].max_id;
	}
	tr[now].sum=tr[now*2].sum+tr[now*2+1].sum;
}
void push_down(ll now){
	tr[now*2].sum+=tr[now*2].sum_len*tr[now].tag;
	tr[now*2].maxz+=tr[now].tag;
	tr[now*2+1].sum+=tr[now*2+1].sum_len*tr[now].tag;
	tr[now*2+1].maxz+=tr[now].tag;
	tr[now*2].tag+=tr[now].tag;
	tr[now*2+1].tag+=tr[now].tag;
	tr[now].tag=0;
}
void tr_build(ll l,ll r,ll now){
	tr[now].l=l,tr[now].r=r;
	tr[now].maxz=0,tr[now].max_id=l;
	if(l==r){
		tr[now].sum_len=len[re_id[l]];
		return;
	}
	ll mid=(l+r)/2;
	tr_build(l,mid,now*2);
	tr_build(mid+1,r,now*2+1);
	tr[now].sum_len=tr[now*2].sum_len+tr[now*2+1].sum_len;
}
ll re_wgt(ll now){
	if(tr[now].l==tr[now].r)return re_id[tr[now].l];
	push_down(now);
//	cout<<now<<" "<<tr[now*2].maxz<<" "<<tr[now*2+1].maxz<<endl;
	if(tr[now*2+1].maxz>=(sum_siz+1)/2)return re_wgt(now*2+1);
	else return re_wgt(now*2);
}
void tr_ad(ll l,ll r,ll w,ll now){
	if(tr[now].l>=l&&tr[now].r<=r){
		tr[now].maxz+=w;
		tr[now].sum+=tr[now].sum_len*w;
		tr[now].tag+=w;
		return;
	}
	push_down(now);
	ll mid=(tr[now].l+tr[now].r)/2;
	if(l<=mid)tr_ad(l,r,w,now*2);
	if(r>mid)tr_ad(l,r,w,now*2+1);
	push_up(now);
	return;
}
ll tr_qs(ll p,ll now){
	if(tr[now].l==tr[now].r)return tr[now].maxz;
	push_down(now);
	ll mid=(tr[now].l+tr[now].r)/2;
	if(p<=mid)return tr_qs(p,now*2);
	else return tr_qs(p,now*2+1);
}
ll tr_re(ll l,ll r,ll now){
	if(tr[now].l>=l&&tr[now].r<=r)return tr[now].sum;
	push_down(now);
	ll mid=(tr[now].l+tr[now].r)/2;
	ll ansz=0;
	if(l<=mid)ansz+=tr_re(l,r,now*2);
	if(r>mid)ansz+=tr_re(l,r,now*2+1);
	return ansz;
}
ll re_(ll x){
	ll ansz=0;
	while(tp[x]){
		ansz+=tr_re(id[tp[x]],id[x],1);
		x=f[tp[x]];
	}
	return ansz;
}
void ad_(ll x,ll w){
	while(tp[x]){
		tr_ad(id[tp[x]],id[x],w,1);
		x=f[tp[x]];
	}
}
int main(){
	freopen("zjoi15_tree.in","r",stdin);
	freopen("zjoi15_tree.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<n;i++){
		ll x=read(),y=read(),w=read();
		build(x,y,w);
		build(y,x,w);
	}
	dfs1(1,0);
	dfs2(1,1);
	tr_build(1,n,1);
//	for(int i=1;i<=n;i++)cout<<id[i]<<" ";
//	cout<<endl;
	for(int i=1;i<=q;i++){
		ll x=read(),y=read();
		S+=y*dep_len[x];
		sum_siz+=y;
		ad_(x,y);
		ll wgt=re_wgt(1);
//		cout<<wgt<<" "<<tr_qs(id[wgt],1)<<" "<<S<<" "<<re_(wgt)*2<<endl;
		cout<<sum_siz*dep_len[wgt]+S-re_(wgt)*2<<endl;
	}
	return 0;
}