P12653 [KOI 2024 Round 2] 分数竞赛

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

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$，以空格分隔。

**约束条件** - 所有输入值均为整数。 - $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 完成