暴力大法吼啊
先跑两遍$dfs$求树的直径，记录下直径上的点，暴力跑从每个点出发不经过直径的的树上最远距离点的路径（领会精神
最后都经过的路径就是答案
某位大佬说的
理论上复杂度$O(n*sum)$当树是一条链时会退化(?)成$O(n^2)$
然而某谷数据水，没判也能A
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 #define int long long 6 const int maxn=2e5+10; 7 const int mod=1e7+7; 8 inline int read(){ 9 int f=1,x=0;char s=getchar(); 10 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 11 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 12 return f*x; 13 } 14 int n,m; 15 struct edge{ 16 int to,nxt,w; 17 }e[maxn*2]; 18 int head[maxn],cnt,d[maxn],vis[maxn],fa[maxn]; 19 int path[maxn],l,r,val[maxn],sum; 20 inline void add(int from,int to,int w){ 21 e[++cnt].to=to;e[cnt].w=w;e[cnt].nxt=head[from];head[from]=cnt; 22 } 23 void Dfs(int x,int len,int fa){ 24 l=max(l,len); 25 for(int i=head[x];i;i=e[i].nxt){ 26 if(e[i].to==fa||vis[e[i].to])continue; 27 vis[e[i].to]=1;Dfs(e[i].to,len+e[i].w,x); 28 } 29 } 30 void dfs(int x){ 31 for(int i=head[x];i;i=e[i].nxt){ 32 if(e[i].to!=fa[x]){ 33 d[e[i].to]=d[x]+e[i].w; 34 fa[e[i].to]=x;dfs(e[i].to); 35 } 36 } 37 } 38 void getd(){ 39 l=1;dfs(1); 40 for(int i=2;i<=n;i++){ 41 if(d[i]>d[l])l=i; 42 } 43 d[l]=0;memset(fa,0,sizeof(fa)); 44 dfs(l); 45 for(int i=2;i<=n;i++){ 46 if(d[i]>d[r])r=i; 47 } 48 } 49 int main(){ 50 n=read(); 51 for(int i=1;i<n;i++){ 52 int u,v,w; 53 u=read();v=read();w=read(); 54 add(u,v,w);add(v,u,w); 55 } 56 getd();printf("%lld ",d[r]); 57 memset(vis,0,sizeof(vis)); 58 for(int i=r;i;i=fa[i]){ 59 vis[i]=1; 60 } 61 for(int i=r;i;i=fa[i]){ 62 l=0;Dfs(i,0,0);val[i]=l; 63 } 64 int j=r; 65 for(int i=fa[r];i;i=fa[i]){ 66 path[i]=j;j=i; 67 } 68 int i; 69 for(i=j;i;i=path[i]){ 70 if(d[r]-d[i]==val[i])break; 71 } 72 for(;i;i=fa[i]){ 73 if(d[i]==val[i])break; 74 sum++; 75 } 76 printf("%lld",sum); 77 return 0; 78 } 79 } 80 signed main(){ 81 gengyf::main(); 82 return 0; 83 }