题解 P3761 【[TJOI2017]城市】
update 2020/7/15 优化了一下 markdown 的用法，增加了前面的题目描述。
题目：
题目描述
从加里敦大学城市规划专业毕业的小明来到了一个地区城市规划局工作。这个地区一共有 n 座城市，n-1 条高速公路，保证了任意两运城市之间都可以通过高速公路相互可达，但是通过一条高速公路需要收取一定的交通费用。小明对这个地区深入研究后，觉得这个地区的交通费用太贵。
小明想彻底改造这个地区，但是由于上司给他的资源有限，因而小明现在只能对一条高速公路进行改造，改造的方式就是去掉一条高速公路，并且重新修建一条一样的高速公路（即交通费用一样），使得这个地区的两个城市之间的最大交通费用最小（即使得交通费用最大的两座城市之间的交通费用最小），并且保证修建完之后任意两座城市相互可达。如果你是小明，你怎么解决这个问题？
输入格式
输入数据的第一行为一个整数 n ，代表城市个数。
接下来的 n - 1 行分别代表了最初的 n - 1 条公路情况。每一行都有三个整数 u,v,d 。u,v 代表这条公路的两端城市标号，d 代表这条公路的交通费用。
1 \leq u,v \leq ， 1\leq d \leq 2000 。
输出格式
输出数据仅有一行，一个整数，表示进行了最优的改造之后，该地区两城市 之间最大交通费用。
首先由
初步解法
我们就可以先有一个 （这一版基本是照着某一楼的题解打出来的）
我们枚举每一条边断开，然后求连个联通块各自的直径，以及两个联通块的最短半径，基本可以说是半个纯暴力。
void Diameter(const int u)//找直径的函数
{
book[u] = 1;//用来标记是否遍历过。
for(reg int i = head[u]; i ; i = e[i].next)
if(!book[e[i].to])
{
Diameter(e[i].to);
int v = f[e[i].to][0] + e[i].wi;
if(v > f[u][0]){f[u][1] = f[u][0];f[u][0] = v;mv[u] = e[i].to;}
else if(v > f[u][1]){f[u][1] = v;}
}
diameter = Max(diameter,f[u][1] + f[u][0]);//很标准的一个求树直径的 DP。
}
void Radius(const int u,const int front)//找半径的函数
{ // front 用来记录自身子树内的最短半径。
book[u] = 0;radius = Min(radius,Max(front,f[u][0]));
for(reg int i = head[u]; i ; i = e[i].next)
if(book[e[i].to]) Radius(e[i].to,Max(front,mv[u] == e[i].to ? f[u][1] : f[u][0]) + e[i].wi);
}
int main()
{
n = Read();
for(reg int i = 1; i < n ; ++i) add_edge(Read(),Read(),Read());
for(reg int i = 2; i <= tot_edge; i += 2)
{
int d1,d2,r1,r2;
diameter = 0;
book[e[i].to]=1;
Diameter(e[i^1].to);
d1 = diameter;
diameter = 0;
Diameter(e[i].to);
d2 = diameter;
book[e[i^1].to]=0;
radius = INF;
Radius(e[i].to,0);
r1 = radius;
radius = INF;
Radius(e[i^1].to,0);
r2 = radius;
Ans = Min(Ans,Max(Max(d1,d2),r1+r2+e[i].wi));
for(reg int i = 1 ; i <= n; ++i) {f[i][0] = mv[i] = f[i][1] = book[i] = 0;}
}
printf("%d",Ans);
return 0;
}如何优化？
优化一：断边
断的边一定在原来树的直径上，且是树所有直径的公共边。
对于非直径上的边，就算断掉，剩下的两个联通块的直径有一个还是原来的直径，所以对其我们要求的答案无影响。
然后直径的非公共边。
如图树的直径有两条，
由此我们可以得到一个优化， 时间复杂度是
void dfs(const int u,const int fa)
{
for(reg int i = head[u]; i ; i = e[i].next)
if(e[i].to != fa)
{
dis[e[i].to] = dis[u] + e[i].wi;
mv[e[i].to] = i;
dfs(e[i].to,u);
}
}
void Diameter(const int u)
{
book[u] = 1;
for(reg int i = head[u]; i ; i = e[i].next)
if(!book[e[i].to])
{
Diameter(e[i].to);
int v = f[e[i].to][0] + e[i].wi;
if(v > f[u][0]){f[u][1] = f[u][0];f[u][0] = v;mv[u] = e[i].to;}
else if(v > f[u][1]){f[u][1] = v;}
}
diameter = Max(diameter,f[u][1] + f[u][0]);
}
void Radius(const int u,const int front)
{
book[u] = 0;radius = Min(radius,Max(front,f[u][0]));
for(reg int i = head[u]; i ; i = e[i].next)
if(book[e[i].to]) Radius(e[i].to,Max(front,mv[u] == e[i].to ? f[u][1] : f[u][0]) + e[i].wi);
}
int main()
{
n = Read();
for(reg int i = 1; i < n ; ++i) add_edge(Read(),Read(),Read());
dfs(1,1);
for(reg int i = 1; i <= n ; ++i) if(dis[S] < dis[i]) S = i;
dis[S] = 0;
for(reg int i = 1; i <= n ; ++i) mv[i] = 0;
dfs(S,S);
for(reg int i = 1; i <= n ; ++i) if(dis[T] < dis[i]) T = i;
for(reg int i = mv[T]; i ; i = mv[e[i^1].to])
ded[++tde] = i;
for(reg int i = 1; i <= n ; ++i) mv[i] = 0;
for(reg int i = 1; i <= tde; i++)//可优化，只删直径
{
int d1,d2,r1,r2;
diameter = 0;
book[e[ded[i]].to]=1;
Diameter(e[ded[i]^1].to);
d1 = diameter;
diameter = 0;
Diameter(e[ded[i]].to);
d2 = diameter;
book[e[ded[i]^1].to]=0;
radius = INF;
Radius(e[ded[i]].to,0);
r1 = radius;
radius = INF;
Radius(e[ded[i]^1].to,0);
r2 = radius;
Ans = Min(Ans,Max(Max(d1,d2),r1+r2+e[ded[i]].wi));
for(reg int i = 1 ; i <= n; ++i) {f[i][0] = mv[i] = f[i][1] = book[i] = 0;}
}
printf("%d",Ans);
return 0;
}优化效果：
从