Codeforces 835F. Roads in the Kingdom

In the Kingdom K., there are n towns numbered with integers from 1 to n. The towns are connected by n bi-directional roads numbered with integers from 1 to n. The i-th road connects the towns ui and vi and its length is li. There is no more than one road between two towns. Also, there are no roads that connect the towns with itself.

Let’s call the inconvenience of the roads the maximum of the shortest distances between all pairs of towns.

Because of lack of money, it was decided to close down one of the roads so that after its removal it is still possible to reach any town from any other. You have to find the minimum possible inconvenience of the roads after closing down one of the roads.


The first line contains the integer n (3 ≤ n ≤ 2·105) — the number of towns and roads.

The next n lines contain the roads description. The i-th from these lines contains three integers uivili (1 ≤ ui, vi ≤ n1 ≤ li ≤ 109) — the numbers of towns connected by the i-th road and the length of the i-th road. No road connects a town to itself, no two roads connect the same towns.

It’s guaranteed that it’s always possible to close down one of the roads so that all the towns are still reachable from each other.


Print a single integer — the minimum possible inconvenience of the roads after the refusal from one of the roads.





前几天 CF div2 的一道题……考场上 WA 了,比完一眼就发现自己外向树直径没考虑进去……




将环上点按顺序排下来,标号 1~k,那么删掉的边有两种,一种是 1 和 k 的连边,一种是其他连边。

如果删掉 1 和 k 的连边,那就变成序列上的问题了,这个等下讲。

如果删掉其他边,那就是把问题拆成左右两边,对于每个点 i,处理出从左端点(不加上点 1 的权值)到 “1 到 i 之间的点” 的距离的最大值,以及 1 ~ i 任意两点间距离最大值。对于 i 右边也要做类似的事情。

那么对于其中删掉 i 和 i + 1 之间的边,得到的树的直径就是 max{左端点到 i 的距离 + 1 和 k 的连边 + (i + 1) 到右端点的距离, 1 ~ i 任意两点距离最大值, (i + 1) ~ k 任意两点最大值}。

如果删掉 1 和 k 的连边,那么树的直径就是上面求出来的,当 i 等于 k 时,1 ~ i 任意两点距离最大值。