CF1656E Equal Tree Sums

给定一棵无向无根树，即一个连通且无环的无向图。 你需要为每个顶点分配一个非零整数权值，使得满足以下条件：如果移除树中的任意一个顶点，则剩下的每个连通分量中所有顶点的权值之和都相等。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$3 \leq n \leq 10^5$），表示树的顶点数。 接下来的 $n-1$ 行，每行包含两个整数 $u, v$（$1 \leq u,v \leq n$），表示顶点 $u$ 和顶点 $v$ 之间有一条边。保证给定的边构成一棵树。 所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试数据，输出一行 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$，其中 $a_i$ 表示分配给第 $i$ 个顶点的权值。权值需满足 $-10^5 \leq a_i \leq 10^5$ 且 $a_i \neq 0$。 可以证明总是存在满足条件的解。如果有多组可行解，输出任意一组均可。

在第一个样例中，当移除顶点 $1$ 时，所有剩余连通分量的权值和均为 $5$；当移除顶点 $3$ 时，所有剩余连通分量的权值和均为 $2$。当移除其他顶点时，剩下的只有一个连通分量，因此所有剩余连通分量的权值和也相等。 由 ChatGPT 4.1 翻译