题解：AT_abc406_f [ABC406F] Compare Tree Weights

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5; 
long long n,m,l[N],r[N],opt,po,po1,tr[N],fa[N],siz[N],son[N],id[N],o,sum,op,op1;
vector<int>q[N];
void add(int i,int j)
{
	while(i<=n)
	{
		tr[i]+=j;
		i+=i&-i;
	}
}
long long cz(int i)
{
	long long ans=0;
	while(i)
	{
		ans+=tr[i];
		i-=i&-i;
	}
	return ans;
}
void dfs(int i)
{
	siz[i]=1;
	for(int j=0;j<q[i].size();++j)
	{
		if(q[i][j]==fa[i]) continue;
		fa[q[i][j]]=i;
		dfs(q[i][j]);
		siz[i]+=siz[q[i][j]];
		if(siz[son[i]]<siz[q[i][j]]) 
			son[i]=q[i][j]; 
	}
}
void dfs1(int i)
{
	++o;
	id[i]=o;
	if(!son[i]) return;
	dfs1(son[i]);
	for(int j=0;j<q[i].size();++j)
	{
		if(q[i][j]==fa[i]||q[i][j]==son[i]) continue;
		dfs1(q[i][j]);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;++i)
		cin>>l[i]>>r[i],q[l[i]].push_back(r[i]),q[r[i]].push_back(l[i]);
	cin>>m;
	dfs(1);
	dfs1(1);
	for(int i=1;i<=n;++i)
		add(i,1),sum+=1;
	for(int i=1;i<=m;++i)
	{
		cin>>opt;
		if(opt==1)
		{
			cin>>op>>op1;
			add(id[op],op1),sum+=op1;
		}
		else{
			cin>>op;
			if(fa[l[op]]==r[op])//看找的是哪一棵子树
				cout<<abs(sum-2*(cz(id[l[op]]+siz[l[op]]-1)-cz(id[l[op]]-1)))<<'\n';
			else
				cout<<abs(sum-2*(cz(id[r[op]]+siz[r[op]]-1)-cz(id[r[op]]-1)))<<'\n';
		}
	}
	return 0;
 }