P1131 [ZJOI2007] Temporal Synchronization

Xiao Q is learning to solder circuit boards in an electronics workshop. A circuit board consists of several components, which we will call nodes, labeled by numbers $1, 2, 3, \cdots$. The nodes on the circuit board are connected by several non-overlapping wires, and for any two nodes on the board, there exists exactly one path (a path is a sequence of wires connecting two components). There is a special component on the board called the “exciter.” When the exciter operates, it generates an excitation current that is sent through wires to each node it is connected to. When an intermediate node receives the excitation current, it gets the information and immediately forwards the current to its connected nodes that have not yet received it. Eventually, the excitation current reaches some “terminal nodes”—nodes that, after receiving the current, no longer forward it. It takes time for the excitation current to travel along a wire. For each edge $e$, the time required for the current to pass through it is $t_e$, while forwarding at nodes is considered instantaneous. The board requires that every terminal node receive the excitation current at the same time—that is, to maintain temporal synchronization. Since the current construction does not meet the synchronization requirement, we need to modify the wiring. Xiao Q has a tool that, when used once, can increase the transmission time of some wire by $1$. What is the minimum number of times the tool must be used to make all terminal nodes temporally synchronized?

- The first line contains an integer $N$, the number of nodes on the circuit board. - The second line contains an integer $S$, the index of the exciter. - The next $N - 1$ lines each contain three integers $a, b, t$, indicating that there is a wire connecting nodes $a$ and $b$, and the excitation current takes $t$ units of time to pass through this wire.

Output a single integer $V$, the minimum number of times the tool must be used.

Constraints: - For $40\%$ of the testdata, $1 \le N \le 1000$. - For $100\%$ of the testdata, $1 \le N \le 5 \times 10^5$. - For all testdata, $1 \le t_e \le 10^6$. Translated by ChatGPT 5