406605: GYM102458 B Daniel and gameshow

Daniel decides to participate in a quite interesting gameshow with others. Below is the description of the game:

Each player will play on a undirected connected graph consisting of $$$n$$$ nodes numbered from 1 to $$$n$$$ and $$$n-1$$$ edges. The rules simply dictates that player starts from a specific node according to Organizing Committee, then moves along the edges to other nodes. Visiting a node and moving through an edge multiple times are acceptable. However, the edge $$$i\ (1\le i\le n-1)$$$ has initial toughness $$$a_i$$$, and each time a player moves through that edge, its toughness decreases $$$1$$$. When its toughness reaches $$$0$$$, the current player and other following players are forbidden to cross that edge.

A player's turn is completed when that player is currently on a node, and they could not move to other node or they decide to terminate. Their score is equal to the number of times they moves through edges of the graph.

The winner is the one with the greatest score.

Daniel is the first player and he wants to maximize his winning chance. Calculate the largest score that Daniel can obtain. Remember, Daniel must start from node $$$R (0\le R\le n)$$$, where $$$R=0$$$ indicates that Daniel could freely pick his starting node.

Line 1 contains an integer $$$n\ (1\le n\le 10^{5})$$$.

Line 2...$$$n$$$: Each line contains three positive integers $$$u, v, r$$$ represents an edge connecting node $$$u$$$ and node $$$v$$$ of the graph $$$(1\le u, v\le n,\ u \ne v)$$$ and its toughness is $$$r\ (1\le r\le 10^{9})$$$.

Line $$$n+1$$$: An integer $$$R (0\le R \le n)$$$

Numbers on the same line are separated by spaces.

A number indicating the maximum score that Daniel can obtain in his turn.

This problem worths 70 points including 6 subtasks:

1. 7 points: Edges connect node $$$1$$$ and node $$$i$$$ with $$$\forall i=\overline{2, n}$$$.
2. 8 points: Edges connect node $$$i$$$ and node $$$i+1$$$ with $$$\forall i=\overline{1, n-1}$$$, $$$R=1$$$.
3. 10 points: Edges connect node $$$i$$$ and node $$$i+1$$$ with $$$\forall i=\overline{1, n-1}$$$, $$$R=0$$$.
4. 14 points: $$$R\ne 0$$$.
5. 15 points: $$$n\le 2000, R = 0$$$
6. 16 points: No other conditions applied.

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

14

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

4

7
1 2 1
1 3 1
2 4 9
2 5 9
3 6 9
3 7 9
1

18

1
1

0