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.

Input

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.

Output

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

Examples

题意简述

给出一棵环套树,边有边权,问删除环上一条边得到的树中,直径最小是多少。

分析

前几天 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 任意两点距离最大值。

比较所有情况的结果求个最小值,再和外向树直径比较,取较大值即可。

 

发表评论