dalao求调 T了 #6 #7 哭!!!
查看原帖
dalao求调 T了 #6 #7 哭!!!
1133645
mazhemg123楼主2024/8/14 11:20
#include<iostream>
using namespace std;
#define int   long long
const int N=200000+20;
int head[N],to[N<<1],Next[N<<1],cnt=1,w[N<<1],n,dist[N],vis[N];
void add(int a,int b,int W){
    to[cnt]=b;
    Next[cnt]=head[a];
    w[cnt]=W;
    head[a]=cnt++;
}
int strat,End,last[N], maxd=-1;
void dfs(int u,int fa,int d){
    last[u]=fa;
    dist[u]=dist[fa]+d;
    for(int j=head[u];j;j=Next[j]){
        int v=to[j];
        if(v!=fa) {
            dfs(v,u,w[j]);
        }
    }
}
 
int maxdist(int u,int f){
     int ans=0;
     for(int i=head[u];i;i=Next[i]){
        int v=to[i];
        if(v!=f&&!vis[v]){
            ans=max(ans,maxdist(v,u)+w[i]);
        }
     }
     return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,W;
        cin>>u>>v>>W;
        add(u,v,W);
        add(v,u,W);
    }
    dfs(1,0,0);
    int start=0;
  
    for(int i=1;i<=n;i++){
         if(maxd<dist[i]){
             maxd=dist[i];
             start=i;
         }
    }
    dfs(start,0,0);
    for(int i=1;i<=n;i++){
        if(maxd<dist[i]){
            maxd=dist[i];
            End=i;
        }
    }
    cout<<dist[End]<<endl;
    for(int i=last[End];i!=0;i=last[i]){
        vis[i]=1;
    }
    int l,r;
     l=start,r=End;
    for(int i=last[End];i!=start;i=last[i]){
       
        int d=maxdist(i,0);
        if(d==dist[End]-dist[i]){
            r=i;
        }
        if(d==dist[i]&&l==start){
            l=i;
        }
    }
    int ans;
    if(l==r)cout<<0<<endl;
    else{
         ans=1;
        for(int i=last[r];i!=l;i=last[i]){
            ans++;
        }
        cout<<ans<<endl;
    }
   //cout<<l<<" "<<r<<" "<<End<<endl;
}
2024/8/14 11:20
加载中...