[数据结构与算法]CodeTON Round 1 (Div. 1 + Div. 2 Rated) E. Equal Tree Sums

E. Equal Tree Sums

https://codeforces.com/contest/1656/problem/E
一道思维题。我们首先定义树上一个点的度为 $deg(v)$ ，然我们先对树 $01$ 染色分类后，令某一类值为 $deg(v)$ ，另一类为 $?deg(v)$ ，这样就满足了题目的条件。为什么呢，我们可以把给某个点赋值 $deg(v)$ 或 $?deg(v)$ 理解为给连接 $v$ 的每条边分摊出 $1$ 或 $?1$ 的权值。假设我们现在删除 $u$ ，那么我们对删除后的连通块求和就是对分摊出去的值求和，我们会发现，对于一个连通块来说，除了这个连通块与 $u$ 原本相连的边以外，其它边被分摊到的值和都为 $0$ 。那么现在就剩下那条被删除的边没考虑，那条删除的边上，属于这个连通块的值，就只有一个 $1$ 或 $?1$ 了，因为我们进行的是 $01$ 染色，所有与 $u$ 相连的点所摊出来的值应当正负号是一样的，所以要么同为 $?1$ ，要么同为 $1$，因为任意连通块的值相等。

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N = 1e6 + 10;

int n, ans[N];
vector<int> g[N];

void dfs(int u, int fa, int f) {
    if (f) ans[u] = (int)g[u].size();
    else ans[u] = -(int)g[u].size();
    for (auto v : g[u]) {
        if (v != fa) {
            dfs(v, u, !f);
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            g[i].clear();
        }
        for (int i = 1; i < n; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, 0, 1);
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", ans[i], i == n ? '\n' : ' ');
        }
    }

}