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 <= i <= 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 <= R <= n)$, where $R = 0$ indicates that Daniel could freely pick his starting node.
Line 1 contains an integer $n " "(1 <= n <= 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 <= u, v <= n, " "u != v)$ and its toughness is $r " "(1 <= r <= 10^9)$.
Line $n + 1$: An integer $R (0 <= R <= 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:
## Input
Line 1 contains an integer $n " "(1 <= n <= 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 <= u, v <= n, " "u != v)$ and its toughness is $r " "(1 <= r <= 10^9)$.Line $n + 1$: An integer $R (0 <= R <= n)$Numbers on the same line are separated by spaces.
## Output
A number indicating the maximum score that Daniel can obtain in his turn.
[samples]
## Scoring
This problem worths 70 points including 6 subtasks: 7 points: Edges connect node $1$ and node $i$ with $forall i = overline(2 , n)$. 8 points: Edges connect node $i$ and node $i + 1$ with $forall i = overline(1 , n -1)$, $R = 1$. 10 points: Edges connect node $i$ and node $i + 1$ with $forall i = overline(1 , n -1)$, $R = 0$. 14 points: $R != 0$. 15 points: $n <= 2000, R = 0$ 16 points: No other conditions applied.
**Definitions**
Let $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = n - 1 $, i.e., a tree.
Let $ E = \{e_1, e_2, \dots, e_{n-1}\} $, where each edge $ e_i = (u_i, v_i) $ has initial toughness $ a_i \in \mathbb{Z}^+ $.
Let $ R \in \{0\} \cup \{1, \dots, n\} $ be the starting constraint: if $ R = 0 $, Daniel may choose any starting node; otherwise, he must start at node $ R $.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, n-1\} $
3. $ 0 \le R \le n $
**Objective**
Daniel traverses the tree starting from node $ R $ (or any node if $ R = 0 $), moving along edges. Each traversal of edge $ e_i $ consumes 1 unit of its toughness; once $ a_i = 0 $, the edge becomes blocked.
Daniel’s score is the total number of edge traversals in his single turn.
He may revisit nodes and edges (as long as toughness > 0), and his turn ends when no more moves are possible or he stops.
Maximize Daniel’s score under optimal play.
**Formulation**
Let $ T = (V, E) $ be the tree.
Define the total traversable edge usage as the sum of all edge toughnesses:
$$
T_{\text{total}} = \sum_{e_i \in E} a_i
$$
Since the graph is a tree, any closed walk must traverse each edge an even number of times to return to the start.
Daniel’s optimal strategy is to traverse the entire tree in a walk that minimizes wasted traversals — i.e., he should aim to traverse each edge at most twice (once in each direction), except for edges along a path from the start to a leaf, which may be traversed only once if the walk ends there.
The maximum number of edge traversals Daniel can achieve is:
$$
\boxed{2 \cdot \sum_{e_i \in E} a_i - \max_{v \in V} \left( \sum_{e_i \in P_{R,v}} a_i \right)}
$$
if $ R \ne 0 $, where $ P_{R,v} $ is the unique path from $ R $ to $ v $.
If $ R = 0 $, then:
$$
\boxed{2 \cdot \sum_{e_i \in E} a_i - \max_{u,v \in V} \left( \sum_{e_i \in P_{u,v}} a_i \right)}
$$
where $ P_{u,v} $ is the unique path between nodes $ u $ and $ v $, i.e., the diameter path in terms of total toughness.
Thus, the maximum score is:
$$
2 \cdot \left( \sum_{e_i \in E} a_i \right) - D
$$
where $ D $ is the maximum total toughness of any simple path in the tree (the “heaviest path” or diameter under edge weights $ a_i $).
**Final Answer**
$$
\boxed{2 \cdot \left( \sum_{e_i \in E} a_i \right) - D}
$$
where $ D = \max_{u,v \in V} \sum_{e_i \in \text{path}(u,v)} a_i $, and the path is taken in the tree $ T $.