题解 CF1656E 【Equal Tree Sums】

enucai · 2022-03-25 13:48:17 · 题解

Preface

膜拜 @Daniel777。

Analysis

考虑子树值的和，分三类讨论：高度为奇数，高度为偶数 与 根。高度为偶数的子树和为 1，高度为奇数的子树和为 -1，根的子树和为 0 即可。Dfs 的时候记录一下深度是奇数还是偶数，再记录一下子树值的和即可。复杂度 O(n)。

Code

Talk is cheap, show me the code.

Codeforces Status

// And in that light, I find deliverance.
#define int long long
int n,a[100010],sum[100010];
vi e[100010];
int col[100010];
void dfs(int u,int fa){
    col[u]=col[fa]^1;
    for(auto v:e[u]) if(v!=fa) dfs(v,u);
}
void solve(int u,int fa){
    for(auto v:e[u]) if(v!=fa) solve(v,u),sum[u]+=sum[v];
    if(u==1) a[u]=0-sum[u];
    else if(col[u]==0) a[u]=1-sum[u];
    else a[u]=-1-sum[u];
    sum[u]+=a[u];
}
void work(){
    read(n);
    For(i,1,n) a[i]=0,e[i].clear(),sum[i]=0;
    For(i,1,n-1){
        int u,v;read(u,v);
        e[u].pb(v),e[v].pb(u);
    }
    col[0]=1;
    dfs(1,0);
    solve(1,0);
    For(i,1,n) cout<<a[i]<<" ";puts("");
}
signed main(){
    int T;read(T);
    while(T--) work();
}