Codeforces Round #427 (Div. 2) F-Roads in the Kingdom (基环树)

F. 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 ui, vi, li (1 ≤ ui, vi ≤ n, 1 ≤ 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

input
3
1 2 4
2 3 5
1 3 1
output
5

input
5
2 3 7
3 1 9
4 1 8
3 5 4
4 5 5
output
18

题目大意

给定一个有n个节点和n条边的图,任意两点相互联通,无自环,无重边,求删掉一条边形成的树的直径的最小值。

易知所给的图中仅有一个环,即为一颗基环树。容易发现只能删环上的边。

显然问题的关键在于删边之后如何快速求出直径。

考虑在环上来讨论,将环上的边编号,下文中均为从 $1$ 到 $m$ 。

可以将直径的来源分为两类,一类为经过环,另一类为不经过环。

首先考虑环上每个节点环外挂着的树的部分,这一部分不会发生变化,可以先求出树的直径。

考虑经过环的部分,设每个点与其环外的树中点的最大距离为 $d_i$

枚举删除环上 $(x,x+1)$ 这条边,那么经过环的路径可以分为三类:1~x中取两个 $d_i$ 再加上环上的一段,x+1~m中取两个 $d_i$ 再加上环上的一段,两部分各取一个 $d_i$ 再加上环上经过边 $(1,m)$ 的一段。

分别处理这三种情况,对于前两种情况,设 $\rm pre_ans[x]$ 表示1~x中第一种路径的最大值, $\rm suf_ans[x]$ 表示x~n中第二种路径的最大值。

计算这两个数组就是一个简单的 $\rm dp$ ,令 $\rm sum[x]$ 表示从环上不经过 $(1,m)$ 这条边从 $1$ 走到 $x$ 的距离,那么只需要记录前面最大的一个 $\rm d[y]-sum[y]$ 就可以算出 $\rm pre_ans[x]$ 了, $\rm suf_ans[x]$ 同理。

考虑最后一部分,那么预处理两个数组, $\rm pre[x]$ 表示1~x中 $\rm d[i]+sum[i]$ 的最大值, $\rm suf[x]$ 表示x~n中 $\rm sum[m]-sum[i]+d[i]$ 的最大值,那么如果删除边 $(x,x+1) $ ,则答案就是 $\rm pre[x]+suf[x+1]$

注意到如果删除 $(1,m)$ 这条边,那么结果就是 $\rm pre_ans[m]$

那么到这里,这道题就解决了。总时间复杂度 $O(n)$ 。


代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#define ll long long
#define N 222222
#define M 444444
using namespace std;
stack<ll>S;
bool vis[N];
ll n,R[N],L[N],H[N],PA[N],SA[N],PL[N],SL[N],tot;
ll TOT,LA[N],NE[M],EN[M],LE[M],d;
ll GM(ll x,ll y,ll z)
{
if(x>=y&&x>=z)return x;
if(y>=z)return y;
return z;
}
void ADD(ll x,ll y,ll z)
{
TOT++;
EN[TOT]=y;
LE[TOT]=z;
NE[TOT]=LA[x];
LA[x]=TOT;
}
ll DFS(ll x,ll f)
{
if(vis[x])return x;
vis[x]=1;S.push(x);
for(ll i=LA[x];i;i=NE[i])
if(EN[i]!=f)
{
ll y=DFS(EN[i],x);
if(y)return y;
}
S.pop();return 0;
}
ll DFSH(ll x,ll f)
{
ll A=0,B=0;
for(ll i=LA[x];i;i=NE[i])
if(EN[i]!=f)
{
B=max(B,DFSH(EN[i],x)+LE[i]);
if(A<B)swap(A,B);
}
d=max(A+B,d);
return A;
}
void FSON(ll x)
{
ll A=0,B=0;
for(ll i=LA[R[x]];i;i=NE[i])
if(EN[i]!=R[x-1]&&EN[i]!=R[x+1])
{
ll y=DFSH(EN[i],R[x]);
B=max(B,y+LE[i]);
if(A<B)swap(A,B);
}
H[x]=A;
d=max(d,A+B);
}
int main()
{
ll i,j,x,y,z,Maxl,TL,ans;
scanf("%I64d",&n);
for(i=1;i<=n;i++)
{
scanf("%I64d%I64d%I64d",&x,&y,&z);
ADD(x,y,z);ADD(y,x,z);
}
x=DFS(1,0);
while(!S.empty())
{
R[++tot]=S.top();
S.pop();
if(R[tot]==x)break;
}
R[tot+1]=R[1];R[0]=R[tot];
for(i=1;i<=tot;i++)
for(j=LA[R[i]];j;j=NE[j])
if(EN[j]==R[i+1]){L[i]=LE[j];break;}
for(i=1;i<=tot;i++)FSON(i);

PA[1]=PL[1]=H[1];
SA[tot]=SL[tot]=H[tot];
SA[tot+1]=-1e18;SL[tot+1]=-1e18;

TL=0;for(i=2;i<=tot;i++)TL+=L[i-1],PL[i]=max(PL[i-1],TL+H[i]);
TL=0;for(i=tot;i>=1;i--)TL+=L[i],SL[i]=max(SL[i+1],TL+H[i]);

Maxl=H[1];
for(i=2;i<=tot;i++)
{
Maxl+=L[i-1];
PA[i]=max(PA[i-1],H[i]+Maxl);
Maxl=max(Maxl,H[i]);
}
Maxl=H[tot];
for(i=tot-1;i>=1;i--)
{
Maxl+=L[i];
SA[i]=max(SA[i+1],H[i]+Maxl);
Maxl=max(Maxl,H[i]);
}
ans=max(d,PA[tot]);
for(i=1;i<=tot;i++)
ans=min(ans,GM(max(d,PA[i]),SA[i+1],PL[i]+SL[i+1]));
cout<<ans;
}