无环连通图->树
求树的直径经典做法:
- 任取一点x,用dist记录,深搜出以x为根结点的最长结点y,则y就是树的直径的一个端点
- 再以y为根结点重复此过程,遍历dist最大值即可
这里直接用增长数组来存放每个结点的所临的所有边,时间复杂度:O(n)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 100010
using namespace std;
int n;
struct Edge
{
int id , w;
};
vector<Edge> h[N];
int dist[N];
void dfs(int u,int father,int distance)
{
dist[u] = distance;
for(Edge node : h[u])
if(node.id != father)
dfs(node.id , u , distance + node.w);
}
int main()
{
scanf("%d",&n);
for(int i = 0;i < n-1;i ++)
{
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);
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",s*10+s*(s + 1ll ) / 2);
return 0;
}