树的直径——树形dp求法

树上任意两节点之间最长的简单路径即为树的「直径」。

树形 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;
}