悬关求调!!!
查看原帖
悬关求调!!!
1399216
_Gloaming_楼主2024/7/17 21:03

马风很好求佬调!!!

因为题解看不懂所以也不知道错在哪里?!!

#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;
}
2024/7/17 21:03
加载中...