P3304 [SDOI2013]直径求助啊,3,4点WA,求大佬帮忙
代码:
#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;
}