P8509 How to Get an npy

As the most charming person in the grade, Steve always finds many things for himself, including but not limited to an npy. Steve has a crush on Ada and tries to get closer to her, but Ada is not very willing.

**Hint: You can read the formal statement at the end of the description.** There are $n$ classrooms on Steve's campus, numbered from $1$ to $n$, connected by $n-1$ corridors. In other words, the classrooms and corridors form a tree. Each corridor has a length $w_i$, and the time to pass through this corridor equals its length. Steve likes to wander around the campus. Of course, he hopes that in the end he can reach either his own classroom $s$ or Ada's classroom $t$. However, the school is too complicated, and Steve does not want to walk back along the way he came, so he comes up with the following plan: For every classroom (except Steve's and Ada's classrooms, where there should be no signs around these two classrooms), place a sign on one edge adjacent to it. Every time he arrives at this classroom, he leaves through the edge with the sign. Steve may appear in any classroom in the school, so on one hand, Steve needs to make sure that from every classroom he can follow the signs back to either his classroom or Ada's classroom. On the other hand, he hopes the **sum of times** from all classrooms in the school to the destination is as small as possible. Since Steve is going to look for Ada again, please help him complete this task. #### Formal statement Given an undirected tree with $n$ nodes and two key nodes $s,t$, orient all edges such that: - Each edge is either directed or deleted. - For every node (except $s,t$), the out-degree is exactly $1$, and for $s,t$ the out-degree is $0$. - From every node, it is possible to reach $s$ or $t$ by following directed edges. Find the minimum possible value of the sum of distances from every node to $s$ or $t$.

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

Output a single positive integer on the first line, representing the minimum total weight sum. On the next line, output a string $S$, where: - $S_i=\texttt{0}$ means no sign is placed on either end of the $i$-th edge. - $S_i=\texttt{1}$ means a sign is placed at $u_i$ of the $i$-th edge. - $S_i=\texttt{2}$ means a sign is placed at $v_i$ of the $i$-th edge. This problem is judged with a custom checker. If multiple solutions exist, output any one.

#### Explanation for Sample 1 `2011` is also a valid answer, but `2211`, `1102`, etc. are not. #### Explanation for Sample 2 The figure below shows an optimal solution for the sample (the edge $(8,13)$ is not drawn):  #### Explanation for Sample 3 This sample satisfies the constraints of Subtask 2. #### Explanation for Sample 4 This sample satisfies the constraints of Subtask 5. --- The provided files also include `checker.cpp`, which can be used to determine whether an output is valid. To use it, first compile it (assume the binary is `checker` (Linux/MacOS) or `checker.exe` (Windows)), then run the following command in the terminal: ``` ./checker in.txt out.txt ans.txt ``` If you are using Windows and cannot run the above command, please try: ``` checker.exe in.txt out.txt ans.txt ``` Here, `in.txt`, `out.txt`, and `ans.txt` are the input file, the contestant'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 you can get full score. - `wrong answer`: the first line is incorrect. - `points 0.60`: the first line is correct, but the second line is incorrect. For all non-full-score cases, there will be an additional message with the following meanings: - `A x y`: the first line is incorrect; the standard answer is $x$, and the contestant's answer is $y$. - `B`: the length of the second line does not meet the requirement. - `C`: the second line contains an invalid character. - `D`: the construction on the second line does not satisfy the degree constraints in the statement. - `E x y`: the construction on the second line produces an answer of $y$, while the actual answer is $x$. This checker may differ from the checker used in the final judging. Note that in the output samples provided with the files, only the optimal value is shown, without a construction. ### Constraints **This problem uses bundled testdata.** For all testdata, $3\le n\le 3\times 10^5$, $1\le w_i\le2\times 10^8$, $1\le s,t\le n$, and $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 & / & / & There\ exists\ an\ edge\ (s,t)\\\hline 6 & 30 & 2\sim5 &/ & / \end{array} $$ If you compute the correct optimal value but your construction is wrong, you will get $60\%$ of the score for that test point. Note that even if you only implement the first part, you should still output any non-empty string on the second line, otherwise you may get no score. In this problem, the dependencies mean: the score ratio of a subtask cannot exceed the score ratio of the subtasks it depends on. For example, if a contestant gets $60\%$ of Subtask $1$, then their Subtask $2$ will not exceed the corresponding $60\%$ score, i.e. not more than $9$ points. The answer can be very large, so please pay attention to the data type you use. --- Until graduation, Steve still did not win Ada over. What a sad story. :-( Translated by ChatGPT 5