树上任意两节点之间最长的简单路径即为树的「直径」。
树形 DP的做法 可以在存在负权边的情况下求解出树的直径。
const int N=10010,M=20010;
int n,a,b,c,ans;
struct edge{int v,w;};
vector<edge> e[N];
int dfs(int x,int fa){
int d1=0,d2=0;
for(auto ed : e[x]){
int y=ed.v, z=ed.w;
if(y==fa) continue;//这样就不用开vis数组了,节约空间
int d=dfs(y,x)+z;
if(d>=d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
ans=max(ans,d1+d2);
return d1;//返回从u点往下走的最大长度(悬挂在u点上的最长路径的长度)
}
int main(){
cin>>n;
for(int i=1; i<n; i++){
cin>>a>>b>>c;
e[a].push_back({b,c});
e[b].push_back({a,c});
}
dfs(1,-1);
cout<<ans;
}
标签:int,ed,dfs,求法,树形,ans,d2,dp,d1
From: https://www.cnblogs.com/mathiter/p/17878126.html