求树的直径的两种算法

书P369~371
①：树形DP
https://www.cnblogs.com/kma093/p/9742317.html

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
const double eps=1e-7;
typedef long long ll;
using namespace std; 
struct edge
{
    int to,nex,w;
}e[maxn]; 
int head[maxn],cnt; 
void add(int u,int v,int w)
{
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].nex=head[u];
    head[u]=cnt++;
}
int ans,dp[maxn][2]; 
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
}
void dfs(int u,int fa)
{
    for(int i=head[u];~i;i=e[i].nex)
    {
        int v=e[i].to,w=e[i].w;
        if(v==fa)continue;
        dfs(v,u);
        if(dp[v][0]+w>dp[u][0])
        {
            dp[u][1]=dp[u][0];
            dp[u][0]=dp[v][0]+w;
        }
        else dp[u][1]=max(dp[u][1],dp[v][0]+w);
    }
    ans=max(ans,dp[u][0]+dp[u][1]);
}
int main()
{ 
   int u,v,w;
   init();
   while(~scanf("%d%d%d",&u,&v,&w))
   add(u,v,w),add(v,u,w);
   dfs(1,-1);
   printf("%d\n",ans);
   return 0;
}

②：两次DFS

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
struct abc
{
    int v,w;
};
int v[maxn];
vector<vector<abc> > a;
abc dfs(int x,int ju)
{
    abc ans;
    ans.v=x;ans.w=ju;
    v[x]=1;
    for(int i=0;i<a[x].size();i++)
    {
        if(v[a[x][i].v]==0)
        {
            abc p=dfs(a[x][i].v,ju+a[x][i].w);
            if(ans.w<=p.w)
            {
                ans.w=p.w;
                ans.v=p.v;
            }
        }
    }
    return ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        a.push_back({});
    }
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        abc r;
        r.v=y;r.w=z;
        a[x].push_back(r);
        r.v=x;
        a[y].push_back(r);
    }
    memset(v,0,sizeof(v));
    abc li=dfs(1,0);
    memset(v,0,sizeof(v));
    li=dfs(li.v,0);
    cout<<li.w<<endl;
    return 0;
}