題目大意：

題目鏈接：https://www.luogu.org/problemnew/show/P4408
給出一棵樹，已知有人一開始在$C$點，要到達$A$點和$B$點（那個近先去哪）。求最壞的情況所需的時間。

---

思路：

轉化題意：
$$求max(dis[A][B]+min(dis[C][A],dis[C][B]))$$
那么為了使答案最大，那么肯定先滿足$dis[A][B]$盡量大，那么肯定就是求樹的直徑。那么假設求出的樹的直徑的兩個端點是$p$和$q$，那么很明顯可以暴力求出每個點到$p$和到$q$的較小值，然后取個$max$即可。
時間復雜度：$O(n)$

---

代碼：

//dfs1和dfs2是求直徑的兩個端點p和q以及直徑長度 //dfs3和dfs4是求每個點到p的距離和到q的距離 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll;const int N=200100; int n,m,x,y,z,tot,p,q,head[N]; ll ans,sum,dis[N];struct edge {int next,to,dis; }e[N*2];void add(int from,int to,int dis) {e[++tot].to=to;e[tot].dis=dis;e[tot].next=head[from];head[from]=tot; }void dfs1(int x,int fa,ll s) {if (s>sum) sum=s,p=x;for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (y==fa) continue;dfs1(y,x,s+e[i].dis);} }void dfs2(int x,int fa,ll s) {if (s>ans) ans=s,q=x;for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (y==fa) continue;dfs2(y,x,s+e[i].dis);} }void dfs3(int x,int fa,ll s) {dis[x]=s;for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (y==fa) continue;dfs3(y,x,s+e[i].dis);} }void dfs4(int x,int fa,ll s) {dis[x]=min(dis[x],s); //在到p的距離和到q的距離中選擇更近的那一個for (int i=head[x];~i;i=e[i].next){int y=e[i].to;if (y==fa) continue;dfs4(y,x,s+e[i].dis);} }int main() {memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dfs1(1,0,0);dfs2(p,0,0);dfs3(p,0,0);dfs4(q,0,0);sum=0;for (int i=1;i<=n;i++)sum=max(sum,dis[i]); //求最大值printf("%lld\n",sum+ans); //直徑+最大值return 0; }

總結

以上是生活随笔為你收集整理的【洛谷P4408】逃学的小孩【树的直径】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。