CF1656E Equal Tree Sums Sol

可以用归纳法解题。

首先发现，删掉一个点，剩下的块数就是它的度数。

不妨使得 \(\sum a_i=0\)，一个点的点权等于其他所有点权的和的相反数。

发现度数是相互提供的，则相邻的点的正负性一定相反。

考虑如何进行具体构造。

设当前点 \(\text{cur}\)，其父亲为 \(\text{f}\)，\(\text{cur}\) 的 \(p\) 棵子树的和均为 \(x\)，剩余连通块的和也为 \(x\)。

那么 \(a_{\text{cur}}=-(p+1)x\)。

考虑转移到 \(\text{f}\)，其以 \(\text{cur}\) 为根的子树和为 \(-(p+1)x+px=-x\)。

同理有其余子树（加上 \(\text{cur}\) 的共 \(q\) 个）和连通块的和为 \(-x\)。

那么 \(a_{\text f}=(q+1)x\)。

以 \(\text{f}\) 为根的子树和为 \((q+1)x-qx=x\)。

那么你会发现，子树和呈交替的 \(x,-x\) 的状态。这是什么原因呢？

其实对于每一棵子树来说，它自己本身就是一个合法状态。

那么此时它只有一个父亲，会贡献 \(1\) 的度数，且由于相邻点权正负性相反，于是存在 \(x,-x\)。

这样构造，子树和就与点权没关系了，只和深度有关，为 \(x\) 或 \(-x\)。

将叶子节点均赋为 \(1\) 或 \(-1\)，往上递归即可（为了保证点权不超过限制）。

稍微想一下发现不需要反过来求和，点权的绝对值其实就是它的度数，正负性由深度决定。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = N << 4;
int t, n, cnt, qu[N], dep[N], lst[N], res[N], head[N];
struct Edge { int to, nxt; } e[N << 1];

namespace fast_io {
    int it, ed, ot, t; char stk[20], bf[N + 50], ob[N + 50];
    #define gc (it == ed && (ed = (it = 0) + fread(bf, 1, N, stdin), it == ed))? EOF : bf[it++]
    template <typename T> inline void read(T &x) {
        x = 0; char ch = gc; int f = 1;
        for (; !isdigit(ch); ch = gc) if (ch == '-') f = -1;
        for (; isdigit(ch); ch = gc) x = x * 10 + (ch ^ 48); x *= f; return ;
    } template <typename T, typename ...Args>
    inline void read(T &x, Args &...args) { read(x), read(args...); }
    inline void fls() { fwrite(ob, 1, ot, stdout), ot = 0; }
    template <typename T> inline void write(T x, char opt) {
        if (x < 0) ob[ot++] = '-', x = -x;
        while (x > 9) stk[++t] = 48 ^ (x % 10), x /= 10;
        for (ob[ot++] = 48 ^ x; t; ob[ot++] = stk[t--]);
        ob[ot++] = opt; if (ot > N) fls(); return ;
    }
} using fast_io::read; using fast_io::write;

inline void addEdge(int u, int v) {
    e[++cnt].to = v, e[cnt].nxt = head[u];
    head[u] = cnt;
}

inline void solve() {
    read(n); cnt = 0; for (int i = 1; i <= n; ++i) head[i] = res[i] = 0;
    for (int i = 1, u, v; i < n; ++i)
        read(u, v), addEdge(u, v), addEdge(v, u), ++res[u], ++res[v];
    int l = 1, r = 1; qu[l] = dep[l] = lst[l] = 1;
    while (l <= r) {
        int f = lst[l], cur = qu[l], dp = dep[l]; ++l;
        for (int i = head[cur]; i; i = e[i].nxt) {
            int to = e[i].to;
            if (to ^ f) ++r, lst[r] = cur, qu[r] = to, dep[r] = -dp;
        }
        res[cur] *= dp;
    }
    for (int i = 1; i <= n; ++i) write(res[i], i == n? '\n' : ' ');
}

int main() {
    read(t); while (t--) solve(); fast_io::fls(); return 0;
}