题解：AT_abc406_f [ABC406F] Compare Tree Weights

· · 题解

因为 2 操作不会真的断开子树，所以发现 2 操作的断开边等价于求权值总和减去一棵子树权值和的两倍的绝对值。

然后题目就变成了单点加，子树查的树上问题，先用 dfs 序下树，再用树状数组维护即可。

code

#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;
 }