CF1656E.Equal Tree Sums

You are given an undirected unrooted tree, i.e. a connected undirected graph without cycles.

You must assign a nonzero integer weight to each vertex so that the following is satisfied: if any vertex of the tree is removed, then each of the remaining connected components has the same sum of weights in its vertices.

给你一棵无向无根树，即一个无环的连通无向图。

你需要为每个顶点分配一个非零整数权重，使得满足以下条件：若移除树中任意一个顶点，则剩余的每个连通分量中各顶点的权重之和均相等。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $n$ ($3 \leq n \leq 10^5$) — the number of vertices of the tree.

The next $n-1$ lines of each case contain each two integers $u, v$ ($1 \leq u,v \leq n$) denoting that there is an edge between vertices $u$ and $v$. It is guaranteed that the given edges form a tree.

The sum of $n$ for all test cases is at most $10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, you must output one line with $n$ space separated integers $a_1, a_2, \ldots, a_n$, where $a_i$ is the weight assigned to vertex $i$. The weights must satisfy $-10^5 \leq a_i \leq 10^5$ and $a_i \neq 0$.

It can be shown that there always exists a solution satisfying these constraints. If there are multiple possible solutions, output any of them.

对于每个测试用例，你必须输出一行包含 $n$ 个以空格分隔的整数 $a_1, a_2, \ldots, a_n$，其中 $a_i$ 表示分配给顶点 $i$ 的权值。这些权值必须满足 $-10^5 \leq a_i \leq 10^5$ 且 $a_i \neq 0$。

可以证明，总存在满足上述约束条件的解。如果存在多个可能的解，输出其中任意一个即可。

In the first case, when removing vertex $1$ all remaining connected components have sum $5$ and when removing vertex $3$ all remaining connected components have sum $2$. When removing other vertices, there is only one remaining connected component so all remaining connected components have the same sum.

在第一种情况下，删除顶点 $1$ 后，所有剩余的连通分量的权值和均为 $5$；删除顶点 $3$ 后，所有剩余的连通分量的权值和均为 $2$。删除其他顶点时，仅剩一个连通分量，因此所有剩余连通分量的权值和自然相同。