1207. 大臣的旅费(dfs求树的直径/图论)

题目：

1207. 大臣的旅费 - AcWing题库

思路： 

dfs求树的直径。 

代码：

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=100100;
struct Edge//边的id以及长度
{
    int id,w;
};

vector<Edge>Node[N];//存储结点Node[i]相连的所以边另一端的结点编号以及边的长度
int dist[N];//距离起始结点的距离

void dfs(int u,int father,int distance)
{
    dist[u]=distance;
    for(auto node:Node[u])//遍历当前结点的所以关联结点
        if(node.id!=father)//不重复
            dfs(node.id,u,distance+node.w);
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        Node[a].push_back({b,c});
        Node[b].push_back({a,c});
    }
    
     int u=1;//以结点1为起点
    dfs(1,-1,0);//找到距离结点1最远的结点
    for(int i=1;i<=n;i++)
        if(dist[i]>dist[u])
            u=i;//距离结点1最远的结点编号为u
            
    dfs(u,-1,0);//以结点u为起点，找到距离结点u的最远的结点u
    for(int i=1;i<=n;i++)
        if(dist[i]>dist[u])
            u=i;//距离结点最远的结点编号为u
            
    int s=dist[u];
    printf("%lld",s*10+(1ll+s)*s/2);
}