如何得到 npy

作为年级第一大风流人物，Steve 总会给自己找很多东西，包括但不限于 npy。Steve 看上了 Ada，并试图接近她，然而 Ada 并不是那么乐意。

**提示：你可以阅读题目描述末尾的形式化题面。** Steve 所在的校园有 $n$ 间教室，编号为 $1$ 到 $n$，有 $n-1$ 条走廊将其连通。也就是说，教室和走廊构成了一棵树。每条走廊都有一定的长度 $w_i$，经过这条走廊的时间等于其长度的数值。 Steve 喜欢在校园里游荡。当然，他希望最后能走到自己的教室 $s$ 或 Ada 的教室 $t$。但由于学校过于错综复杂，且 Steve 不想走回头路，所以他想到了如下方案： 对于每个教室（Steve 和 Ada 的教室除外，这两个教室周围不应该有任何标牌），在一条与其相连的边立上标牌。每次走到这个教室，就从立了标牌的边出。 Steve 可能会在学校的任何一个教室出现，所以一方面，Steve 需要让他从每个教室都能跟着标牌回到他的或 Ada 的教室。另一方面，他希望从学校所有教室走到目的地的**时间总和**尽可能小。 由于 Steve 又要去找 Ada 了，所以请你帮他完成这个任务。 #### 形式化题意 给定一棵 $n$ 个节点的无根树和两个关键点 $s,t$，要求对所有边定向，满足： - 每条边要么是有向边，要么被删除； - 每个点（除 $s,t$）出度恰好为 $1$，$s,t$ 出度为 $0$； - 每个点都可以顺着有向边到达 $s$ 或 $t$。 求每个点到 $s$ 或 $t$ 的距离总和最小值。

第一行输入三个正整数 $n$，$s$，$t$。 接下来 $n-1$ 行，每行输入三个正整数 $u_i$，$v_i$，$w_i$，代表一条树边 $(u_i,v_i)$，权值为 $w_i$。

输出第一行一个正整数，代表最小的权值和。 接下来一行，输出一个字符串 $S$，要求： - $S_i=\texttt{0}$，指第 $i$ 条边两边均不立标牌； - $S_i=\texttt{1}$，指第 $i$ 条边在 $u_i$ 处立标牌； - $S_i=\texttt{2}$，指第 $i$ 条边在 $v_i$ 处立标牌。 本题使用自定义校验器评测。如果有多种方案，输出任意一种。

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

4
2201

13 4 5
1 3 3
2 3 2
6 4 5
7 4 10
4 8 2
11 8 3
5 13 6
8 13 5
8 3 4
10 5 8
12 10 3
13 9 9

85
111121202112

见下发文件 corridor/corridor3.in

见下发文件 corridor/corridor3.ans

见下发文件 corridor/corridor4.in

见下发文件 corridor/corridor4.ans

#### 样例 1 解释 `2011` 也是合法的答案，但 `2211`，`1102` 等都不是。 #### 样例 2 解释 下图是取到样例中最优解的状态（$(8,13)$ 这条边没有画出）:  #### 样例 3 解释 该样例满足子任务 2 的限制条件。 #### 样例 4 解释 该样例满足子任务 5 的限制条件。 --- 下发文件中还有 `checker.cpp` 可判定答案是否合法。使用时，先编译（设二进制文件为 `checker`（Linux/MacOS）或 `checker.exe`（Windows）），然后在终端输入如下命令： ``` ./checker in.txt out.txt ans.txt ``` 如果你使用了 Windows 系统且无法运行上述命令，请尝试： ``` checker.exe in.txt out.txt ans.txt ``` 其中 `in.txt`、`out.txt`、`ans.txt` 分别是放在同一目录下的输入文件、选手输出、标准答案。 结果可能有如下中的一种： - `ok`：结果正确，可以得到满分； - `wrong answer`：第一行答案错误； - `points 0.60`：第一行答案正确，第二行答案错误。 对于所有非满分情况，会有附加消息，意义如下： - `A x y`：第一行答案错误，标准答案是 $x$，选手答案是 $y$； - `B`：第二行长度不符合条件； - `C`：第二行出现非法字符； - `D`：第二行给出的构造不满足题目中关于度数的限制； - `E x y`：第二行给出的构造产生的答案是 $y$，而实际上答案是 $x$。 该校验器和最终评测时采用的校验器可能有所不同。 注意下发文件的输出样例中只有最优答案，没有构造方案。 ### 数据规模与约定 **本题捆绑测试**。对于所有数据，$3\le n\le 3\times 10^5$，$1\le w_i\le2\times 10^8$，$1\le s,t\le n$，$s\neq t$。 $$ \def\arraystretch{1.5} \begin{array}{c|c|c||c|c}\hline \bf 子任务 & \bf 分值 & \bf 依赖 & n\le & \bf特殊性质 \\ \hline \hline 1 & 10 & / & 10 & /\\\hline 2 & 15 & 1 & 18 & /\\\hline 3 & 15 & / & / & v_i=u_i+1\\\hline 4 & 10 & / & / & u_i=1\\\hline 5 & 20 & / & / & 存在边\ (s,t)\\\hline 6 & 30 & 2\sim5 &/ & / \end{array} $$ 如果你计算出了正确的答案，但是你的构造是错误的，那你将得到该测试点 $60\%$ 的分数。注意即使你只实现了第一小问，请依旧在第二行输出任意一个非空字符串，否则可能会不计分。 本题中的依赖指：某子任务的得分占比不能超过其所依赖的子任务得分占比。比如，一选手子任务 $1$ 得到 $60\%$ 的分数，则他的子任务 $2$ 就不会超过对应的 $60\%$ 分数，即不超过 $9$ 分。 答案可能很大，请注意你使用的数据类型。 --- 到毕业为止，Steve 也没有追到 Ada。What a sad story. :-(