P15043 [UOI 2022 II Stage] Graph

The city where Xonia lives consists of $n$ intersections, which are connected by $n$ undirected roads. The intersections are numbered from $1$ to $n$. The roads are also numbered from $1$ to $n$. The $i$-th road connects intersections $a_i$ and $b_i$, and its length is $c_i$. It is known that using the existing roads, you can travel from any intersection to any other intersection. Between any two intersections, there is at most one road. There is no road that connects an intersection to itself. Let $dist(x, y)$ be the length of the shortest path between intersections $x$ and $y$. Xonia wants to find two intersections $u$ and $v$ in the city such that $dist(u, v)$ is the maximum among all possible pairs $(u, v)$.

The first line contains two integers $n$ and $g$ ($3 \leq n \leq 200\,000$, $0 \leq g \leq 5$), representing the number of intersections in the city and the test group number, respectively. The next $n$ lines each contain three integers $a_i$, $b_i$, and $c_i$ ($1 \leq a_i, b_i \leq n$, $1 \leq c_i \leq 10^9$). It is guaranteed that using the roads you can travel from any intersection to any other intersection. It is guaranteed that there is no road that connects an intersection to itself. It is guaranteed that between any two intersections there is at most one road.

Output the maximum value of $dist(u, v)$ over all pairs of intersections $(u, v)$.

### Sample Explanation Explanation for the first sample: $dist(1, 2) = 1$ $dist(1, 3) = 2$ $dist(1, 4) = 4$ $dist(2, 3) = 3$ $dist(2, 4) = 3$ $dist(3, 4) = 6$ Therefore, the maximum $dist(u, v) = 6$. ### Scoring - (22 points): The graph structure is a simple cycle. - (17 points): $n \leq 200$. - (24 points): The length of each cycle in the graph does not exceed 1000. - (9 points): $c_i = 1$. - (28 points): No additional constraints. Translated by DeepSeek V3. Translated by ChatGPT 5