马风很好求佬调!!!
因为题解看不懂所以也不知道错在哪里?!!
#include<bits/stdc++.h>
using namespace std;
#define N 200100
#define ll long long
struct node
{
int v,u;
ll w;
}e[N];
int cnt=0,n,k,maxd;
int h[N],fa[N],dis[N],isol[N];
void add(int v,int u,int w)
{
cnt++;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].u=h[u];
h[u]=cnt;
}
void dfs(int now,int f)
{
fa[now]=f;
for(int i=h[now];i;i=e[i].u)
{
int v=e[i].v;
if(!v^f)
continue;
dis[v]=dis[now]+e[i].w;
dfs(v,now);
}
}
void work(int now,int f)
{
maxd=max(maxd,dis[now]);
for(int i=h[now];i;i=e[i].u)
{
int v=e[i].v;
if(f==v)
continue;
dis[v]=dis[now]+e[i].w;
if(dis[v]>dis[k])
k=v;
dfs(v,now);
}
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(v,u,w);
add(u,v,w);
}
dfs(1,0);
k=1;
for(int i=1;i<=n;i++)
{
if(dis[k]<dis[i])
k=i;
}
int st=k;//链的左端点
memset(dis,0,sizeof(0));
dfs(k,0);
for(int i=1;i<=n;i++)
{
if(dis[k]<dis[i])
k=i;//找到链的右端点
}
cout<<dis[k]<<"\n";
memset(dis,0,sizeof(0));
for(int i=k;i;i=fa[i])
isol[i]=1;
int l=st,r=k,ch=0;
for(int i=fa[k];i!=st;i=fa[i])
{
int id=dis[i];
int ip=dis[k]-dis[i];
maxd=dis[i]=0;
work(i,0);
if(maxd==id && !ch) l=i,ch=1;
else if(maxd==ip) r=i;
}
ll ans=0;
for(int i=r;i!=l;i=fa[i])
ans++;
cout<<ans<<"\n";
return 0;
}