80分求助,WA了3,4两个点
查看原帖
80分求助,WA了3,4两个点
550317
TainityAnle楼主2022/7/27 13:12

代码:

#include<iostream> 
#include<string>
#include<cstdio>
using namespace std;
struct ds{
    int to,nxt,cnt,w;
}edge[400005];
int head[200005],cnt=1,n,x,y,ww,st,ks,ans,maxn;
long long maxx;
void add(int u,int v,int ww){
    edge[cnt].to=v;
    edge[cnt].nxt=head[u];
    edge[cnt].w=ww;
    head[u]=cnt++;
}
void dfs(int t,int die,long long dis){
    if(dis>maxx){
        maxx=dis;
        st=t;
    }
    for(int i=head[t];i;i=edge[i].nxt){
        int er=edge[i].to;
        if(er==die) continue;
        dfs(er,t,dis+edge[i].w);
    }
}
int dfs1(int t,int die,long long dis){
    if(dis==maxx) return 1;
    int flag=0;
    for(int i=head[t];i;i=edge[i].nxt){
        int er=edge[i].to;
        if(er==die) continue;
        int tmp=dfs1(er,t,dis+edge[i].w);
        if(tmp){
            edge[i].cnt+=tmp;
            if(edge[i].cnt>maxn){
                maxn=edge[i].cnt;
                ans=1;
            }else if(edge[i].cnt==maxn) ans++;
            flag+=tmp;
        }
    }
    return flag;
}
int main (){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x>>y>>ww;
        add(x,y,ww);
        add(y,x,ww);
    }
    dfs(1,0,0);
    ks=st;
    dfs(ks,0,0);
    cout<<maxx;
    dfs1(ks,0,0);
    cout<<endl<<ans-1;
    return 0;
}
2022/7/27 13:12
加载中...