「TJOI2017」城市

发表于 | 分类于 | | 浏览量： 次

正解复杂度为$O(n^2)$的题感觉越来越少了QwQ。

传送门

洛谷P3761

BZOJ4890

题解

首先比较显然的是断开的边一定是在直径上的。

所以可以枚举直径上断开的边，然后考虑怎样连边才能使之后的最远距离最小。

可以对断开边之后的两棵子树分别进行树形DP，求出每棵子树中与每个点距离最远的点的距离。

那么新连的边的两个端点必定为两棵子树中与该点的最远距离最小的点。

这样连边后的直径为两个端点的最远距离之和加上新连边的长度。

注意新的直径不能比两棵子树的直径小。

代码

写的又臭又长QwQ。

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5005,inf=0x3F3F3F3F;
int n,tot,lnk[maxn],son[maxn*2],w[maxn*2],nxt[maxn*2],idx,dfn[maxn],siz[maxn],sum,rt,Ver[maxn],E[maxn],u,v,ans,F[maxn][4];bool flg,vis[maxn*2];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y,int z){tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
void DFS(int now,int fa,int dist)
{
	if(dist>sum){sum=dist;rt=now;}
	for(int i=lnk[now];i;i=nxt[i])
		if(son[i]!=fa)
			DFS(son[i],now,dist+w[i]);
}
void DFS2(int now,int fa)
{
	dfn[now]=++idx;siz[now]=1;
	if(!flg) Ver[++Ver[0]]=now;
	if(now==v){flg=true;return;}
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(son[i]!=fa)
		{
			if(!flg) E[++E[0]]=i;
			DFS2(son[i],now);
			siz[now]+=siz[son[i]];
			if(!flg) E[0]--;
		}
	}
	if(!flg) Ver[0]--;
}
void DFS3(int now,int fa)
{
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(son[i]!=fa&&!vis[i])
		{
			DFS3(son[i],now);
			if(F[son[i]][0]+w[i]>=F[now][0])
			{
				F[now][2]=F[now][0];
				F[now][3]=F[now][1];
				F[now][0]=F[son[i]][0]+w[i];
				F[now][1]=son[i];
			}
			else if(F[son[i]][0]+w[i]>F[now][2])
			{
				F[now][2]=F[son[i]][0]+w[i];
				F[now][3]=son[i];
			}
			if(F[son[i]][2]+w[i]>F[now][2]&&son[i]!=F[now][1])
			{
				F[now][2]=F[son[i]][2]+w[i];
				F[now][3]=son[i];
			}
		}
	}
}
void DFS4(int now,int fa)
{
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(son[i]!=fa&&!vis[i])
		{
			if(F[now][1]!=son[i])
			{
				if(F[now][0]+w[i]>=F[son[i]][0])
				{
					F[son[i]][2]=F[son[i]][0];
					F[son[i]][3]=F[son[i]][1];
					F[son[i]][0]=F[now][0]+w[i];
					F[son[i]][1]=now;
				}
				else if(F[now][0]+w[i]>F[son[i]][2])
				{
					F[son[i]][2]=F[now][0]+w[i];
					F[son[i]][3]=now;
				}
			}
			if(F[now][3]!=son[i]&&F[now][2]+w[i]>=F[son[i]][0])
			{
				F[son[i]][2]=F[son[i]][0];
				F[son[i]][3]=F[son[i]][1];
				F[son[i]][0]=F[now][2]+w[i];
				F[son[i]][1]=now;
			}
			else if(F[now][3]!=son[i]&&F[now][2]+w[i]>=F[son[i]][2])
			{
				F[son[i]][2]=F[now][2]+w[i];
				F[son[i]][3]=now;
			}
			DFS4(son[i],now);
		}
	}
}
inline void Solve()
{
	for(int i=1;i<Ver[0];i++)
	{
		vis[E[i]]=vis[(E[i]&1)?E[i]+1:E[i]-1]=true;
		memset(F,0,sizeof(F));
		DFS3(Ver[i],0);DFS3(Ver[i+1],0);
		DFS4(Ver[i],0);DFS4(Ver[i+1],0);
		int Max=0,Min1=inf,Min2=inf;
		for(int j=1;j<=n;j++)
		{
			if(dfn[Ver[i]]<=dfn[j]&&dfn[j]<=dfn[Ver[i]]+siz[Ver[i]]) Min1=min(Min1,F[j][0]);
			else Min2=min(Min2,F[j][0]);
			Max=max(Max,F[j][0]);
		}
		if(max(Max,Min1+Min2+w[E[i]])<ans) ans=max(Max,Min1+Min2+w[E[i]]);
		vis[E[i]]=vis[(E[i]&1)?E[i]+1:E[i]-1]=false;
	}
}
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int a=read(),b=read(),c=read();
		add_e(a,b,c);add_e(b,a,c);
	}
	DFS(1,0,0);sum=0;u=rt;
	DFS(u,0,0);ans=sum;v=rt;
	DFS2(u,0);
	Solve();
	printf("%d\n",ans);
	return 0;
}