← 返回题目列表

Codeforces · 1656/E

E. 树总和相等

中文机器翻译题面 查看原题

给你一个无向无根树,即没有循环的连通无向图。

您必须为每个顶点分配一个非零整数权重,以便满足以下条件:如果删除树的任何顶点,则每个剩余​​的连接组件在其顶点中具有相同的权重总和。

输入

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

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

输出 #1

-3 5 1 2 2
1 1 1

注意

在第一种情况下,当删除顶点 $$$1$$$ 时,所有剩余的连接组件的总和为 $$$5$$$,而当删除顶点 $$$3$$$ 时,所有剩余的连接组件的总和为 $$$2$$$。删除其他顶点时,只有一个剩余的连通分量,因此所有剩余的连通分量具有相同的总和。