← 返回题目列表

Codeforces · 1205/D

D. 几乎全部

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

给你一棵有 $$$n$$$ 个节点的树。您必须在其边缘写入非负整数,以便满足以下条件:

对于每两个节点 $$$i$$$, $$$j$$$,查看它们之间的路径并计算该路径边缘上的数字之和。将所有得到的和写在黑板上。然后从 $$$1$$$ 到 $$$\lfloor \frac{2n^2}{9} \rfloor$$$ 的每个整数都必须至少在黑板上写一次。

保证存在这样的安排。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 节点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$),这意味着节点 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证这些边形成一棵树。

输出

输出 $$$n-1$$$ 行,每行形式为 $$$u$$$ $$$v$$$ $$$x$$$ ($$$0 \le x \le 10^6$$$),这意味着你在 $$$u$$$ 和 $$$v$$$ 之间的边缘写下了数字 $$$x$$$。

边集 $$$(u, v)$$$ 必须与输入图的边集一致,但您可以按任何顺序输出边。您还可以按照与输入顺序不同的顺序输出边的末端。

示例

输入 #1

3
2 3
2 1

输出 #1

3 2 1
1 2 2

输入 #2

4
2 4
2 3
2 1

输出 #2

4 2 1
3 2 2
1 2 3

输入 #3

5
1 2
1 3
1 4
2 5

输出 #3

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

注意

在第一个示例中,节点 $$$1$$$ 和 $$$2$$$ 之间的距离等于 $$$2$$$,节点 $$$2$$$ 和 $$$3$$$ 之间到 $$$1$$$,$$$1$$$ 和 $$$3$$$ 到 $$$3$$$ 之间的距离等于 $$$3$$$。

在第三个例子中,从$$$1$$$到$$$9$$$(含)的数字将被写在黑板上,而我们只需要从$$$1$$$到$$$5$$$就可以通过测试。