← 返回题目列表

Codeforces · 1646/D

D. 给树加权

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

给你一棵由 $$$n$$$ 顶点组成的树,编号从 $$$1$$$ 到 $$$n$$$。树是无环的连通无向图。

对于每个 $$$i=1,2, \ldots, n$$$,令 $$$w_i$$$ 为第 $$$i$$$ 个顶点的权重。如果一个顶点的权重等于其所有邻居权重的总和,则该顶点被称为好顶点。

最初,所有节点的权重均未分配。为树的每个顶点分配正整数权重,使得树中好顶点的数量最大化。如果有多种方法可以做到这一点,则必须找到一种使树中所有顶点的权重之和最小化的方法。

输入

第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 树中的顶点数。

然后是 $$$n−1$$$ 行。它们每个都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u,v\le n$$$) 表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证边形成一棵树。

输出

在第一行中打印两个整数 - 良好顶点的最大数量以及该最大值的最小可能权重总和。

在第二行中打印 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$1\le w_i\le 10^9$$$) — 分配给每个顶点的相应权重。可以证明存在满足这些约束条件的最优解。

如果有多个最优解,您可以打印任意一个。

示例

输入 #1

4
1 2
2 3
2 4

输出 #1

3 4
1 1 1 1

输入 #2

3
1 2
1 3

输出 #2

2 3
1 1 1

输入 #3

2
1 2

输出 #3

2 2
1 1

输入#4

9
3 4
7 6
2 1
8 3
5 6
1 8
8 6
9 6

输出#4

6 11
1 1 1 1 1 1 1 3 1

注意

这是第一个测试用例的树:

这是第二个测试用例的树: