rt,模拟赛中出现了求有权无向树的直径,想请教一下大佬为什么下面的代码一个 AC,一个WA。
WA:
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1e5+5;
struct edge{
int v,w;
};
vector<edge> p[N];
int len,dep,x;
void dfs(int u,int fa,int now){
for (int i=0;i<p[u].size();i++){
edge e=p[u][i];
int v=e.v,w=e.w;
if (v!=fa){
if (dep<now){
dep=now;
x=v;
}
dfs(v,u,now+w);
}
}
}
void dfs2(int u,int fa,int now){
for (int i=0;i<p[u].size();i++){
edge e=p[u][i];
int v=e.v;
if (v!=fa){
len=max(len,now+e.w);
dfs2(v,u,now+e.w);
}
}
}
signed main(){
int n;
cin>>n;
for (int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
p[u].pb((edge){v,w});
p[v].pb((edge){u,w});
}
dfs(1,0,0);
dfs2(x,0,0);
int ans=len;
cout<<ans;
return 0;
}
AC:
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1e5+5;
struct edge{
int v,w;
};
vector<edge> p[N];
int len,dep[N],tmp,x;
void dfs(int u,int fa){
for (int i=0;i<p[u].size();i++){
edge e=p[u][i];
int v=e.v,w=e.w;
if (v!=fa){
dep[v]=dep[u]+w;
if (dep[v]>dep[x]) x=v;
dfs(v,u);
}
}
}
void dfs2(int u,int fa,int now){
for (int i=0;i<p[u].size();i++){
edge e=p[u][i];
int v=e.v;
if (v!=fa){
len=max(len,now+e.w);
dfs2(v,u,now+e.w);
}
}
}
signed main(){
// freopen("pay.in","r",stdin);
// freopen("pay.out","w",stdout);
int n;
cin>>n;
for (int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
p[u].pb((edge){v,w});
p[v].pb((edge){u,w});
}
dfs(1,0);
dfs2(x,0,0);
int ans=len;
cout<<ans;
return 0;
}
区别在于第一次 dfs 时找最深点的方式。