题解：AT_abc406_f [ABC406F] Compare Tree Weights

#include<cstdio>
#include<cstring>
#include<iostream>
#define int long long
using namespace std;
const int MAXN=500010;
const int mod=1e9+7;
struct Node{
	int v,nxt;
}e[MAXN*2];
int n,m;
int son[MAXN],f[MAXN];
int siz[MAXN],Top[MAXN],dep[MAXN];
int id[MAXN],nw[MAXN];
int h[MAXN],tot,cnt;
int eu[MAXN],ev[MAXN],out[MAXN];
struct node{
	int l,r;
	long long dat,laz;
}tr[MAXN*4];
int a[MAXN];
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].dat=nw[l];
		return;
	}
	int mid=(l+r)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	tr[p].dat=(tr[2*p].dat+tr[2*p+1].dat);
}
void spread(int p){
	if(tr[p].laz){
		tr[2*p].dat+=(tr[2*p].r-tr[2*p].l+1)*tr[p].laz;
		tr[2*p+1].dat+=(tr[2*p+1].r-tr[2*p+1].l+1)*tr[p].laz;
		tr[2*p].laz+=tr[p].laz;
		tr[2*p+1].laz+=tr[p].laz;
		tr[p].laz=0;
	}
}
void Change(int p,int l,int r,long long k){
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].dat+=(tr[p].r-tr[p].l+1)*k;
		tr[p].laz+=k;
		return;
	}
	spread(p);
	int mid=(tr[p].l+tr[p].r)/2;
	if(l<=mid) Change(2*p,l,r,k);
	if(r>mid) Change(2*p+1,l,r,k);
	tr[p].dat=(tr[2*p].dat+tr[2*p+1].dat);
}
long long ask(int p,int l,int r){
	if(l<=tr[p].l&&tr[p].r<=r) return tr[p].dat;
	spread(p);
	int mid=(tr[p].l+tr[p].r)/2;
	long long val=0;
	if(l<=mid) val+=ask(2*p,l,r);
	if(r>mid) val+=ask(2*p+1,l,r);
	return val;
}
void add(int x,int y){
	e[++tot].v=y;
	e[tot].nxt=h[x];
	h[x]=tot;
}
void dfs1(int u,int fa){
	siz[u]=1;
	f[u]=fa;
	dep[u]=dep[fa]+1;
	for(int i=h[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void dfs2(int root,int t){
	Top[root]=t;
	id[root]=++cnt;
	nw[cnt]=a[root];
	if(!son[root]){
		out[root]=cnt;
		return;
	}
	dfs2(son[root],t);
	for(int i=h[root];i;i=e[i].nxt){
		int v=e[i].v;
		if(v!=f[root]&&v!=son[root]) dfs2(v,v);
	}
	out[root]=cnt;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) a[i]=1;
	for(int i=1;i<n;i++){
		cin>>eu[i]>>ev[i];
		add(eu[i],ev[i]);
		add(ev[i],eu[i]);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	cin>>m;
	while(m--){
		int t,x;
		cin>>t>>x;
		if(t==1){
			int w;
			cin>>w;
			Change(1,id[x],id[x],w);
        }else{
			int u=eu[x],v=ev[x];
			if(dep[u]>dep[v]) swap(u,v);
			int s=ask(1,id[v],out[v]);
			int ans=ask(1,1,n);
			cout<<abs(ans-2*s)<<"\n";
		}
	}
	return 0;
}