{"raw_statement":[{"iden":"background","content":"作为年级第一大风流人物，Steve 总会给自己找很多东西，包括但不限于 npy。Steve 看上了 Ada，并试图接近她，然而 Ada 并不是那么乐意。"},{"iden":"statement","content":"**提示：你可以阅读题目描述末尾的形式化题面。**\n\nSteve 所在的校园有 $n$ 间教室，编号为 $1$ 到 $n$，有 $n-1$ 条走廊将其连通。也就是说，教室和走廊构成了一棵树。每条走廊都有一定的长度 $w_i$，经过这条走廊的时间等于其长度的数值。\n\nSteve 喜欢在校园里游荡。当然，他希望最后能走到自己的教室 $s$ 或 Ada 的教室 $t$。但由于学校过于错综复杂，且 Steve 不想走回头路，所以他想到了如下方案：\n\n对于每个教室（Steve 和 Ada 的教室除外，这两个教室周围不应该有任何标牌），在一条与其相连的边立上标牌。每次走到这个教室，就从立了标牌的边出。\n\nSteve 可能会在学校的任何一个教室出现，所以一方面，Steve 需要让他从每个教室都能跟着标牌回到他的或 Ada 的教室。另一方面，他希望从学校所有教室走到目的地的**时间总和**尽可能小。\n\n由于 Steve 又要去找 Ada 了，所以请你帮他完成这个任务。\n\n#### 形式化题意\n\n给定一棵 $n$ 个节点的无根树和两个关键点 $s,t$，要求对所有边定向，满足：\n\n- 每条边要么是有向边，要么被删除；\n- 每个点（除 $s,t$）出度恰好为 $1$，$s,t$ 出度为 $0$；\n- 每个点都可以顺着有向边到达 $s$ 或 $t$。\n\n求每个点到 $s$ 或 $t$ 的距离总和最小值。"},{"iden":"input","content":"第一行输入三个正整数 $n$，$s$，$t$。\n\n接下来 $n-1$ 行，每行输入三个正整数 $u_i$，$v_i$，$w_i$，代表一条树边 $(u_i,v_i)$，权值为 $w_i$。"},{"iden":"output","content":"输出第一行一个正整数，代表最小的权值和。\n\n接下来一行，输出一个字符串 $S$，要求：\n\n- $S_i=\\texttt{0}$，指第 $i$ 条边两边均不立标牌；\n- $S_i=\\texttt{1}$，指第 $i$ 条边在 $u_i$ 处立标牌；\n- $S_i=\\texttt{2}$，指第 $i$ 条边在 $v_i$ 处立标牌。\n\n本题使用自定义校验器评测。如果有多种方案，输出任意一种。"},{"iden":"note","content":"#### 样例 1 解释\n\n`2011` 也是合法的答案，但 `2211`，`1102` 等都不是。\n\n#### 样例 2 解释\n\n下图是取到样例中最优解的状态（$(8,13)$ 这条边没有画出）:\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/78tlf89y.png)\n\n#### 样例 3 解释\n\n该样例满足子任务 2 的限制条件。\n\n#### 样例 4 解释\n\n该样例满足子任务 5 的限制条件。\n\n---\n\n下发文件中还有 `checker.cpp` 可判定答案是否合法。使用时，先编译（设二进制文件为 `checker`（Linux/MacOS）或 `checker.exe`（Windows）），然后在终端输入如下命令：\n\n```\n./checker in.txt out.txt ans.txt\n```\n\n如果你使用了 Windows 系统且无法运行上述命令，请尝试：\n\n```\nchecker.exe in.txt out.txt ans.txt\n```\n\n其中 `in.txt`、`out.txt`、`ans.txt` 分别是放在同一目录下的输入文件、选手输出、标准答案。\n\n结果可能有如下中的一种：\n\n- `ok`：结果正确，可以得到满分；\n- `wrong answer`：第一行答案错误；\n- `points 0.60`：第一行答案正确，第二行答案错误。\n\n对于所有非满分情况，会有附加消息，意义如下：\n\n- `A x y`：第一行答案错误，标准答案是 $x$，选手答案是 $y$；\n- `B`：第二行长度不符合条件；\n- `C`：第二行出现非法字符；\n- `D`：第二行给出的构造不满足题目中关于度数的限制；\n- `E x y`：第二行给出的构造产生的答案是 $y$，而实际上答案是 $x$。\n\n该校验器和最终评测时采用的校验器可能有所不同。\n\n注意下发文件的输出样例中只有最优答案，没有构造方案。\n\n### 数据规模与约定\n\n**本题捆绑测试**。对于所有数据，$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$。\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{c|c|c||c|c}\\hline\n\n\\bf 子任务 & \\bf 分值 & \\bf 依赖 & n\\le & \\bf特殊性质\n\\\\\n\\hline\n\\hline\n1 & 10 & / & 10 & /\\\\\\hline\n2 & 15 & 1 & 18 & /\\\\\\hline\n3 & 15 & / & / & v_i=u_i+1\\\\\\hline\n4 & 10 & / & / & u_i=1\\\\\\hline\n5 & 20 & / & / & 存在边\\ (s,t)\\\\\\hline\n6 & 30 & 2\\sim5 &/ & /\n\\end{array}\n$$\n\n如果你计算出了正确的答案，但是你的构造是错误的，那你将得到该测试点 $60\\%$ 的分数。注意即使你只实现了第一小问，请依旧在第二行输出任意一个非空字符串，否则可能会不计分。\n\n本题中的依赖指：某子任务的得分占比不能超过其所依赖的子任务得分占比。比如，一选手子任务 $1$ 得到 $60\\%$ 的分数，则他的子任务 $2$ 就不会超过对应的 $60\\%$ 分数，即不超过 $9$ 分。\n\n答案可能很大，请注意你使用的数据类型。\n\n---\n\n到毕业为止，Steve 也没有追到 Ada。What a sad story. :-("}],"translated_statement":null,"sample_group":[["5 1 5\n1 2 1\n2 3 1\n3 4 1\n4 5 1","4\n2201"],["13 4 5\n1 3 3\n2 3 2\n6 4 5\n7 4 10\n4 8 2\n11 8 3\n5 13 6\n8 13 5\n8 3 4\n10 5 8\n12 10 3\n13 9 9","85\n111121202112"],["见下发文件 corridor/corridor3.in","见下发文件 corridor/corridor3.ans"],["见下发文件 corridor/corridor4.in","见下发文件 corridor/corridor4.ans"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}