求解树的直径的思路和实现（两次dfs或者bfs）

树的直径定义：在带有边权的树中（连通无回路的图），**距离最远的两个点之间的各边边权之和**，成为树的直径
求解思路：1、先在树的节点中任选一个点作为起点，dfs一遍，找到其他点距离起点最远的点的编号。
          2将此点作为新的起点，再dfs一遍，找到距离此点的最远距离的点的编号并求解出这两点的距离（边权重和）

大臣的旅费

两次dfs

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100010;
int dist[N];
struct Edge   //边存储成结构体形式，存储节点编号和边的权重
{
    int id,w;
};
vector<Edge>h[N];  //一共有n个点，每个点都需要一个vector
int n;
void dfs(int u,int father,int d)
{
    dist[u]=d;
    for (auto node:h[u])
    {
        if (node.id!=father)
            dfs(node.id,u,node.w+dist[u]);
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n-1;i++)  //n个点 n-1条边
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        h[a].push_back({b,c});  //无向图，要存两次
        h[b].push_back({a,c});
    }

    dfs(1,-1,0); //假设从1号点开始，这里任选1个点作为起点即可

    int u=1;  //找出其他点到起点距离的最大值的点的编号
    for (int i=1;i<=n;i++)
        if (dist[i]>dist[u])
            u=i;

    dfs(u,-1,0); //此点作为新的起点

    for (int i=1;i<=n;i++)  //找出其他点距离新起点的距离的最大值以及对应的点的编号
        if (dist[i]>dist[u])
            u=i;
    int s=dist[u];
    printf("%lld\n",10*s+s*(s+1ll)/2);  
    return 0;
}

两次bfs

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010, M = 2*N;  //无向图，一条边需要存两次
int h[M],e[M],ne[M],idx,w[M];
int dist[N]; //表示每个点到其他点的距离
int n;
bool st[N]; //bfs搜索过程的判重数组
void add(int a,int b,int c)  //邻接表法板子
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void bfs(int u)  
{
    queue<int>q;
    q.push(u);
    dist[u]=0;
    st[u]=true;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if (!st[j])
            {
                dist[j]=dist[t]+w[i];
                st[j]=true;
                q.push(j);
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    memset(h,-1,sizeof h);  
    for (int i=0;i<n-1;i++)  //读入n-1条边
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);  //无向图
    }
    memset(dist,0x3f,sizeof dist);
    bfs(1);

    int u=1;
    for (int i=1;i<=n;i++)
        if (dist[i]>dist[u])
            u=i;
    memset(st,false,sizeof st);  //恢复
    memset(dist,0x3f,sizeof dist);
    bfs(u);

    for (int i=1;i<=n;i++)
        if (dist[i]>dist[u])
            u=i;
    int ans=dist[u];
    printf("%lld\n",10*ans+ans*(ans+1ll)/2);
    return 0;
}