题解：AT_abc406_f [ABC406F] Compare Tree Weights

EDG_AKUYTRE · 2025-05-21 16:12:15 · 题解

前言：本文提供树链剖分做法。

第一种操作很好处理，只需要单独给节点 x 加上 w 即可，即代码中的 Change(1,id[x],id[x],w)。

对于第二种操作，对于边 y 连接点 u 与点 v ，假设 v 是较深节点：

设 v 的子树权值为 s ，整棵树的权值为 sum ，差值计算为 |sum - 2*s| （因为另一子树权重为 sum-s ）1。

代码：

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

提交记录

完结！