update 2020/7/15 優化了一下 \(markdown\) 的用法，增加了前面的題目描述。 題目： 題目描述 從加里敦大學城市規劃專業畢業的小明來到了一個地區城市規劃局工作。這個地區一共有 \(n\) 座城市，\(n-1\) 條高速公路，保證了任意兩運城市之間都可以通過高速公路相互可達， ...
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 $。
輸出格式
輸出數據僅有一行，一個整數，表示進行了最優的改造之後，該地區兩城市 之間最大交通費用。
首先由 $n \leq 5000 $ ,時間限制是 \(3s\) 我們可以確定本題 \(O(n^2)\)可以卡過去。
初步解法
我們就可以先有一個 \(O(n^2)\) 的暴力解法。
（這一版基本是照著某一樓的題解打出來的）
我們枚舉每一條邊斷開，然後求連個聯通塊各自的直徑，以及兩個聯通塊的最短半徑，基本可以說是半個純暴力。
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;
}
如何優化？
優化一：斷邊
斷的邊一定在原來樹的直徑上，且是樹所有直徑的公共邊。
對於非直徑上的邊，就算斷掉，剩下的兩個聯通塊的直徑有一個還是原來的直徑，所以對其我們要求的答案無影響。
然後直徑的非公共邊。
如圖樹的直徑有兩條， $ 1->8 $ 和 $ 1->9 $ ，斷掉 $ 5->6,5->7,6->9,7->8$ 中的任意一條，都不會讓剩下的兩個聯通塊的直徑減小，所以其對答案也無影響。
（這裡的性質使選原樹任意一條直徑進行刪邊都可以找到正確答案所刪的那一條邊）
由此我們可以得到一個優化， 時間複雜度是 $ O(nL)$ , \(L\) 是原樹直徑的邊數。
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;
}
優化效果：
從 $ 17.55s -> 1.61s $,掛了氧氣能達到 \(871ms\) 。
\(O(n^2)\)
\(O(nL)\)
氧氣
優化二：連邊
\(1.\) 2如果連的是直徑上的點，那麼可以確定新樹的直徑是兩個聯通塊直徑上的較長鏈相加，為了使其儘可能短，所以我們要連兩個聯通塊直徑的中點來使較長鏈更短。
\(2.\) 如果連的不是直徑上的點，那麼可以確定新樹的直徑是兩個聯通塊直徑上的較長鏈相加在加上連接點到各自直徑的距離，是一定長於 方案 \(1\) 的。
所以可以寫一個找直徑中點的函數代替上文中找半徑的函數。
這個函數時間複雜度很難算，姑且可當做 \(\Omega(1)\) ，卡一卡就變 \(O（L）\) 了。
可以證明的是聯通塊上的直徑一定有一半以上的長度是與原樹直徑重合的（只需要理解一下上文用 \(DP\) 求直徑的做法)，可以用這個性質來找中點。
這個優化代碼我沒單獨寫
int rt=0,lt=0,Half = ans>>1,cur;
cur = i;
while(dp[cur][0] - WW[cur] > Half && cur) cur = mvv[cur];
rt = dp[cur][0];
cur = mv[i];
Half = (f[mv[i]][0] + f[mv[i]][1])>>1;
while(f[cur][0] - W[cur]> Half && cur) cur = mv[cur];
lt = f[cur][0];
ans = Max(ans,W[i] + lt + rt);
終極優化
調了很久也沒調出來。
我們在直徑上遍歷刪邊的時候，不難發現做了很多的重覆的遍歷。
黃色是斷了的邊。
對於斷邊左側：從上往下的過程中，紅色的點進行了多餘的遍歷，只有橙色的點才是需要遍歷的。
對於斷邊右側：我們發現若是從最左邊的點進行第一次遍歷，那麼我們便已經得到了右聯通塊需要的所有信息。
在找右邊直徑的過程都是可以通過 \(O(n)\) 預處理變成 \(O(1)\) 的。
在找左邊直徑的過程可以用 \(book\) 數組標記，不重覆遍歷，也可以實現整體 \(O(n)\)的。
最終加上連邊的優化是可以達到 \(\Omega(n)\)？
需要特別註意的是，會有特殊的數據如圖：
就是如圖所示，刪去 \(6 -> 1\) 的邊後最長鏈不經過 \(1\) 點，這需要特殊處理。
即斷的邊的端點不一定在斷邊後聯通塊的直徑上。
我的想法就是先找到最長鏈的兩個端點，再分別從兩個端點跑一次 \(dfs\) 。
要記錄兩個東西。
當前子樹直徑。
據當前子樹根節點最近的直徑上的節點。
void dfs1(const int u,const int fa)
{
for(reg int i = head[u]; i ; i = e[i].next)
if(e[i].to != fa)
{
dfs1(e[i].to,u);
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;W[u] = e[i].wi;}
else if(v > f[u][1]){f[u][1] = v;}
A[u] = Max(A[u],A[e[i].to]);
}
A[u] = Max(A[u],f[u][1] + f[u][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)
{
dfs(e[i].to,u);
int v = dp[e[i].to][0] + e[i].wi;
if(v > dp[u][0]){dp[u][1] = dp[u][0];dp[u][0] = v;mvv[u] = e[i].to;WW[u] = e[i].wi;}
else if(v > dp[u][1]){dp[u][1] = v;}
B[u] = Max(B[u],B[e[i].to]);
}
B[u] = Max(B[u],dp[u][1] + dp[u][0]);
}
記錄每一個子樹的最長鏈，次長鏈，然後斷的邊移動，但是不用 \(DP\) 了，可以直接從數組中找到當前情況下各聯通塊的直徑，最後找一下對應直徑中點就可以找到答案了。
