AdditionalFile5627.zip

#5627. 「POI2026 R2」Dwukolorowe drzewo

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – II etap Dwukolorowe drzewo

Bajtazar 的花园里长着一棵树。它由编号为 $1$ 到 $n$ 的 $n$ 个节点组成，其中 $n$ 为偶数。这棵树包含 $n-1$ 条树枝，每条树枝直接连接两个节点。此外，正如树木通常的情况，每对节点之间存在唯一一条由不重复树枝组成的路径。

比特托邦的国旗日即将到来，因此 Bajtazar 决定将树中一半的节点染成白色，另一半染成黑色，使其看起来像比特托邦的国旗（由于比特托邦人重视和谐与对称，他们的国旗由一半白色和一半黑色组成）。我们将任何这样的染色方案称为国旗染色。

然而，Bajtazar 如果不提出些奇怪的要求就不是他了。他认为国旗染色的美感取决于所有同色节点对之间的距离之和。这里两节点之间的距离是指连接它们的路径上的树枝数量。

Bajtazar 希望这个总和尽可能大。请帮助他找到这个最大和，以及达到该最大和的任意一种国旗染色方案！

输入格式

第一行包含一个偶数 $n$ $(1 \leq n \leq 10^{6})$，表示树中的节点数量。

接下来的 $n-1$ 行包含树枝的描述。第 $i$ $(1 \leq i \leq n-1)$ 行包含两个整数 $a_{i}, b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示节点 $a_{i}$ 和 $b_{i}$ 之间由一条树枝直接相连。

输出格式

第一行输出在给定树的节点国旗染色方案中，同色节点对之间距离的最大和。

第二行输出一个由 $n$ 个字符组成的字符串，描述达到该总和的国旗染色方案。在该字符串中，第 $i$ $(1 \leq i \leq n-1)$ 个字符如果是 0，表示节点 $i$ 被染成白色；如果是 1，表示它被染成黑色。

样例

输入

6
1 2
2 4
2 3
1 5
5 6

输出

14
011001

上述样例中的树如下图所示。节点按照示例输出中的结果进行染色。白色节点（标注为 0）之间的路径包括：节点 $1$ 和 $5$（长度为 $1$）、$1$ 和 $4$（长度为 $2$）以及 $5$ 和 $4$（长度为 $3$）。黑色节点（标注为 1）之间的路径包括：节点 $2$ 和 $3$（长度为 $1$）、$2$ 和 $6$（长度为 $3$）以及 $3$ 和 $6$（长度为 $4$）。这些路径长度的总和为 $1+2+3+1+3+4=14$。可以证明，无法获得更大的同色节点对路径长度之和。

附加样例

1. $n=16$，节点 $i$ 与节点 $i-2$ 相连（对于 $3 \leq i \leq n$），且节点 $8$ 与节点 $9$ 相连。
2. $n=24$，所有编号大于 $1$ 的节点均与节点 $1$ 相连。
3. $n=5000$，编号从 $3$ 到 $2501$ 的节点均与节点 $1$ 相连，编号从 $2502$ 到 $5000$ 的节点均与节点 $2$ 相连，且节点 $1$ 与节点 $2$ 相连。
4. $n=100000$，节点 $i$ 与节点 $i-1$ 相连（对于 $2 \leq i \leq n$）。
5. $n=1000000$，节点 $i$ 与节点 $\lfloor i / 2 \rfloor$ 相连（对于 $2 \leq i \leq n$）。

数据范围与提示

详细子任务附加限制及分值如下表所示。

如果你只输出了正确的第一行（即最大和），你的程序将获得该测试点 $50\%$ 的分数。为了获得这部分分数，你不需要输出第二行。