Background

As the most charming person in the grade, Steve is always on the lookout for various things, including, but not limited to, a significant other (npy). Steve has taken a liking to Ada and is trying to get closer to her, but Ada is not very receptive.

Problem Description

Hint: You can read the formal problem statement at the end of the description.

Steve's campus has $n$ classrooms numbered from $1$ to $n$, connected by $n-1$ corridors. This means that the classrooms and corridors form a tree structure. Each corridor has a certain length $w_i$, and the time to traverse a corridor is equal to its length.

Steve enjoys wandering around the campus. Of course, he hopes to eventually reach his own classroom $s$ or Ada's classroom $t$. However, due to the complex layout of the school and Steve's reluctance to backtrack, he has come up with the following plan:

For each classroom (excluding Steve's and Ada's classrooms, as no signs should be placed around these two), place a sign on one of the edges connected to it. Whenever he reaches this classroom, he will exit through the edge with the sign.

Since Steve could appear in any classroom on campus, on one hand, he needs to ensure that he can follow the signs back to his or Ada's classroom from any classroom. On the other hand, he wants the total time it takes to reach the destination from all classrooms to be as small as possible.

Since Steve is about to go look for Ada again, please help him complete this task.

Formal Problem Statement

Given an undirected tree with $n$ nodes and two key points $s, t$, the task is to orient all edges such that:

• Each edge is either directed or deleted;
• Each node (except $s, t$) has exactly one outgoing edge, and $s, t$ have no outgoing edges;
• Every node can reach $s$ or $t$ by following the directed edges.

Find the minimum sum of distances from each node to $s$ or $t$.

Input Format

The first line contains three positive integers $n$, $s$, and $t$.

The next $n-1$ lines each contain three positive integers $u_i$, $v_i$, and $w_i$, representing a tree edge $(u_i, v_i)$ with weight $w_i$.

Output Format

The first line contains a single positive integer representing the minimum total weight.

The next line contains a string $S$ where:

• $S_i = \texttt{0}$ means the $i$-th edge has no signs;
• $S_i = \texttt{1}$ means the $i$-th edge has a sign at $u_i$;
• $S_i = \texttt{2}$ means the $i$-th edge has a sign at $v_i$.

This problem uses a custom checker for evaluation. If there are multiple solutions, output any one.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4
2201

Sample Input #2

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

Sample Output #2

85
111121202112

Sample Input #3

See the provided file corridor/corridor3.in

Sample Output #3

See the provided file corridor/corridor3.ans

Sample Input #4

See the provided file corridor/corridor4.in

Sample Output #4

See the provided file corridor/corridor4.ans

Notes/Hints

Sample 1 Explanation

2011 is also a valid answer, but 2211, 1102, etc., are not.

Sample 2 Explanation

The diagram below shows the state that yields the optimal solution in the sample (the edge $(8, 13)$ is not shown):

Sample 3 Explanation

This sample satisfies the constraints of Subtask 2.

Sample 4 Explanation

This sample satisfies the constraints of Subtask 5.

The provided file checker.cpp can be used to verify the correctness of the answer. To use it, compile it first (let the binary file be checker (Linux/MacOS) or checker.exe (Windows)), and then enter the following command in the terminal:

./checker in.txt out.txt ans.txt

If you are using Windows and cannot run the above command, try:

checker.exe in.txt out.txt ans.txt

Where in.txt, out.txt, and ans.txt are the input file, the player's output, and the standard answer, respectively, placed in the same directory.

The result may be one of the following:

• ok: The result is correct and full marks can be obtained.
• wrong answer: The first line of the answer is incorrect.
• points 0.60: The first line of the answer is correct, but the second line is incorrect.

For non-full-mark situations, additional messages will be provided with the following meanings:

• A x y: The first line of the answer is incorrect, the standard answer is $x$, and the player's answer is $y$.
• B: The length of the second line does not meet the conditions.
• C: The second line contains illegal characters.
• D: The construction given in the second line does not meet the degree constraints in the problem.
• E x y: The answer produced by the construction in the second line is $y$, while the actual answer is $x$.

The checker provided and the one used for final evaluation may differ.

Note that the provided output samples only contain the optimal answers, not the construction plans.

Data Size and Constraints

This problem is bundled test cases. For all data, $3 \leq n \leq 3 \times 10^5$, $1 \leq w_i \leq 2 \times 10^8$, $1 \leq s, t \leq n$, $s \neq t$.

$$ \def\arraystretch{1.5} \begin{array}{c|c|c||c|c}\hline \bf Subtask & \bf Points & \bf Dependencies & n\le & \bf Special Properties \\ \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 & / & / & Exists edge\ (s,t)\\\hline 6 & 30 & 2\sim5 &/ & / \end{array} $$

If you have calculated the correct answer but your construction is incorrect, you will receive $60\%$ of the points for that test case. Note that even if you only implement the first part, please still output a non-empty string on the second line, otherwise, you may not receive any points.

The dependencies in this problem mean that the score of a subtask cannot exceed the score of its dependent subtasks. For example, if a player scores $60\%$ on subtask 1, then their score for subtask 2 will not exceed $60\%$ of the points, i.e., not more than 9 points.

The answer may be very large, so be mindful of the data types you use.

Until graduation, Steve never managed to win over Ada. What a sad story. :-(

见题面 Input 部分

见题面 Output 部分