【學習筆記】[圖論]樹的直徑

非嚴格定義：在一棵帶權樹上，相聚距離最大的兩個點或最長鏈的長度，稱之為樹的直徑

樣例輸入：

4
1 2 10
1 3 12
1 4 15

樣例輸出

27

似乎並沒有什麼難理解的地方。

解法1：DP

咕著

解法2：DFS

經過思考，發現一個重要的性質：離樹上的某一結點最遠的那個結點，定是直徑的一個端點。

那麼就好辦了！找到任一點的最遠點，再找到這個最遠點的遠點，這條路徑就是樹的直徑。所以需要兩次 DFS 。

#include <iostream>
#include <cstdio>
#include <cstring>

const int N=1000010;

using namespace std;

int n,m,head[N],tot,dis[N],cur,mx;
//mx是最遠距離

struct Edge
{
    int to,next,val;
};
Edge G[N<<1];

inline int read()
{
    int w=1,s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void addedge(int u,int v,int w)
{
    G[++tot]=(Edge){v,head[u],w},head[u]=tot;
    G[++tot]=(Edge){u,head[v],w},head[v]=tot;
}

inline void dfs(int u,int fa)
{
    for(int i=head[u];i;i=G[i].next)
    {
        int v=G[i].to;if(v==fa)continue;
        dis[v]=dis[u]+G[i].val;
        if(dis[v]>mx)cur=v,mx=dis[v];
        dfs(v,u);
    }
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read(),w=read();
        addedge(u,v,w);
    }
    dfs(1,0);mx=0;memset(dis,0,sizeof(dis));
    //清空上一次 dfs 記錄的狀態
    dfs(cur,0); //從上一次找到的端點開始再次尋找
    cout<<mx<<endl;
    return 0;
}