CF1656E Equal Tree Sums

题目链接

分析

1. 对树进行二分染色( $color = 0/1$ )
2. 对于结点 $u$，若 $color(u)=0$，则将其赋值为 $deg(u)$；否则赋值为 $-deg(u)$。（$deg(u)$ 代表结点 $u$ 的度数）
3. 结论：经过步骤 2，树上各结点权值和为 0。
   证明：对于任意一个 $color=0$ 的结点 $u$，其权值 $deg(u)$ 来自于与其直接相连的 $deg(u)$ 个 $color=1$ 的结点（注意：$color=1$ 的结点权值为负）。而且，结点 $u$ 也为直接相连的 $deg(u)$ 个结点的权值各自贡献 $-1$。即结点 $u$ 本身的权值正好抵消掉它给相邻结点贡献的权值。同理可证：对于任意一个 $color=1$ 的结点也有相同的结论。综上，经过步骤 2，树上各结点权值和为0。
4. 进一步深究结论 3：删除结点 $u$ 后，与 $u$ 直接连接的结点各自属于一颗子树。此时结点 $u$ 本身的权值 $deg(u)$ 没有了，但是它对相邻结点的影响却没有删除（即各自 $-1$）。若不考虑结点 $u$ 的影响，由结论 3 可知：与 $u$ 直接连接的结点各自所在的子树的权值和为 0，现由于结点 $u$ 给每一颗子树都 $-1$，故各子树的权值和为 $-1$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+5;

int n;
array<int, MAXN> ans;
vector<int> G[MAXN];
array<bool, MAXN> vis;
void dfs(int now, int color) {
    if (color)
        ans[now] = G[now].size();
    else
        ans[now] = -G[now].size();
    vis[now] = 1;
    for (int v: G[now]) {
        if (!vis[v])
            dfs(v, color ^ 1);
    }
}
int main() {
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    int t, u, v;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            G[i].clear();
        vis = {};

        for (int i = 0; i < n - 1; i++) {
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 1);
        for (int i = 1; i <= n; i++) {
            cout << ans[i] << " ";
        }
        cout << "\n";
    }

    return 0;
}