解题思路:
链式前向星+深搜
参考代码:
#include<iostream> #include<cstring> using namespace std; const int N = 100010 , M = 200010; int h[N] ,e[M], ne[M] ,w[M],idx; int f[N]; void add(int a,int b,int c){ e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++; } void dfs(int u,int fa,int dis){ f[u]=dis; for(int i=h[u];i!=-1;i=ne[i]){ int j = e[i]; if(j!=fa) dfs(j,u,f[u]+w[i]); } } signed main(){ int n; cin>>n; memset(h,-1,sizeof h); for(int i=0;i<n-1;i++){ int a,b,c; cin>>a>>b>>c; add(a,b,c); add(b,a,c); } dfs(1,-1,0); int u = 1; for(int i=2;i<=n;i++) if(f[i]>f[u]) u=i; dfs(u,-1,0); int _max = f[1]; for(int i=2;i<=n;i++) if(f[i]>_max) _max=f[i]; cout<<(_max * 10 + ((long)(_max + 1) * _max ) / 2); return 0; }
0.0分
0 人评分