题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

KOI 公园由编号从 $1$ 到 $N$ 的 $N$ 个地点组成，地点之间通过 $N-1$ 条道路相连。第 $i$ 条道路连接 $U_i$ 号地点和 $V_i$ 号地点，具有权值 $W_i$（$1 \le i \le N-1$）。

KOI 公园中的任意两个地点都可以通过这些道路相互到达，也就是说，这是一棵树结构。

KOI 公园即将举行一场分数竞赛，其规则如下：

• 总共有 $N - 1$ 名选手，每人从起点出发，沿着一条简单路径（即不重复经过任何地点）前往除起点以外的一个不同终点。
• 每名选手起始分数为 0。
• 每经过一条道路，选手便会获得该道路的分数（可以是负数）。
• 选手可以在任意时刻将当前分数归零，包括到达终点之后。

最大化某位选手最终得分的一个策略是：每当当前得分为负时，立刻将其归零。我们称这种策略为最优策略。所有选手都会采用此策略。

对于每一个起点 $i$（$1 \le i \le N$），设在 $i$ 为起点时，所有选手在遵循最优策略后最终得分的总和为 $S_i$，所有选手将分数归零的总次数为 $C_i$。

例如，考虑下图所示的 KOI 公园结构，当 $1$ 号地点为起点时：

• 前往 $2$ 号地点的选手经过 $-1$ 分的道路，到达后归零，最终得分为 0。
• 前往 $3$ 号地点的选手经过 $+2$ 分的道路，最终得分为 2。
• 前往 $4$ 号地点的选手先经过 $-1$ 分到达 $2$ 号，再归零，然后经过 $+2$ 分到达 $4$，最终得分为 2。
• 前往 $5$ 号地点的选手先经过 $+2$ 分到达 $3$ 号，再经过 $-3$ 分到达 $5$，在 $5$ 号归零，最终得分为 0。
• 前往 $6$ 号地点的选手先经过 $+2$ 分到达 $3$ 号，再经过 $-1$ 分到达 $6$，最终得分为 1。

因此，$S_1 = 5$，$C_1 = 3$。

请编写程序，计算每个起点 $i$ 的 $S_i$ 和 $C_i$。

输入格式

第一行输入一个整数 $N$。
接下来的 $N-1$ 行中，第 $i$ 行输入三个整数 $U_i\ V_i\ W_i$，表示第 $i$ 条道路的两端节点及其权值。

输出格式

若只计算 $S_1, \ldots, S_N$：

• 第一行输出整数 0。
• 第二行输出 $S_1\ S_2\ \ldots\ S_N$，以空格分隔。

若同时计算 $S_1, \ldots, S_N$ 和 $C_1, \ldots, C_N$：

• 第一行输出整数 1。
• 第二行输出 $S_1\ S_2\ \ldots\ S_N$，以空格分隔。
• 第三行输出 $C_1\ C_2\ \ldots\ C_N$，以空格分隔。

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

1
5 5 6 8 6 6
3 5 2 0 6 6

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

1
51 75 71 47 51 47 47 91 51 91
0 0 0 0 0 0 0 0 0 0

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

1
24 23 40 48 21 23 24 24 24 21
11 12 2 0 12 4 1 3 9 4

提示

约束条件

• 所有输入值均为整数。
• $2 \le N \le 300\,000$
• $1 \le U_i, V_i \le N \quad (1 \le i \le N - 1)$
• $-10^7 \le W_i \le 10^7 \quad (1 \le i \le N - 1)$

子任务

1. （2 分）$N \le 1\,000$
2. （6 分）$0 \le W_i \le 5$
3. （20 分）$0 \le W_i \le 5$ 或 $W_i \le -1\,000\,000$
4. （4 分）$U_i = 1,\ V_i = i+1$
5. （10 分）$U_i = i,\ V_i = i+1$
6. （16 分）$U_i = \left\lfloor \frac{i+1}{2} \right\rfloor,\ V_i = i+1$
7. （18 分）与三条及以上道路直接相连的地点最多有两个
8. （24 分）无额外约束

若仅计算 $S_1, \ldots, S_N$，可获得该子任务一半的分数。详细请参考输出格式说明。
若计算了 $S_1, \ldots, S_N$ 和 $C_1, \ldots, C_N$，但 $C$ 值不准确，即使 $S$ 正确，也无法得分。

在洛谷上需要正确输出正确的 $S_1, \ldots, S_N$ 和 $C_1, \ldots, C_N$ 才可以获得分数。

翻译由 ChatGPT-4o 完成