Equal Tree Sums

题意翻译

给定一个包含 $n$ 个节点的无根树。请给这棵树上的每个点赋一个绝对值不超过 $10^5$ 的非零权值，使得当树上任意一个节点被移除时，所有被分开的部分的点权和相等。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $3\leqslant n\leqslant 10^5$。 Translated by Eason_AC

题目描述

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 $ .

输出格式

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.

输入输出样例

输入样例 #1

2
5
1 2
1 3
3 4
3 5
3
1 2
1 3

输出样例 #1

-3 5 1 2 2
1 1 1

说明

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.