Acwing.1207 大臣的旅费_综合

树的直径

任取一点x
找到距x最远的一点y，y与据y最远的点之间的距离就是直径

Acwing.1207 大臣的旅费

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int dis[N];//需要找到从任意一个点a出发距离最远的点b，距离点b最远的点与b的距离即为树的直径//创建一个结构体存储每条路的权值
struct Edge{
    int s,w;//s代表下一个结点的坐标，w代表路程长度
};vector<Edge> h[N];void dfs(int start,int father,int distance){
    dis[start]=distance;for(auto t:h[start])//遍历当前结点的所有相邻结点，if(t.s!=father) dfs(t.s,start,distance+t.w);//防止回溯到父节点造成循环
}int main(){
    cin>>n;int a,b,c;for(int i=1;i<n;i++){
    scanf("%d%d%d",&a,&b,&c);h[a].push_back({
    b,c});h[b].push_back({
    a,c});}dfs(1,-1,0);//用dfs遍历一遍整棵树，记录每条路径的长度int u=1;for(int i=1;i<=n;i++)if(dis[i]>dis[u]) u=i;dfs(u,-1,0);//从b点遍历，距离最远的即为直径for(int i=1;i<=n;i++)if(dis[i]>dis[u]) u=i;int s=dis[u];cout<<s*10+s*(s+1ll)/2;//路费计算公式return 0;
}