Find the longest chain on the tree (or the diameter of the tree, the distance between the two furthest points on the tree, the maximum value of all shortest path distances in the tree)
1. Tree-shaped DP (can effectively handle negative edge weights)
2. Twice dfs or bfs (cannot handle negative edge weights)
Dance without a boss
Figure 1 A dance party without a boss
Maximum value of two non-adjacent points in the tree
#include<bits/stdc++.h>
using namespace std;
const int MAX=6010;
int ne[MAX],e[MAX],idx,h[MAX];
int f[MAX][2],w[MAX];
bool sta[MAX];
void add(int a,int b)
{ e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{ f[u][1]=w[u]; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; dfs(j); f[u][0]+=max(f[j][0],f[j][1]); f[u][1]+=f[j][0]; }
}
int main()
{ int n; cin>>n; for(int i=1;i<=n;i++)cin>>w[i]; memset(h,-1,sizeof(h)); for(int i=0;i<n-1;i++) { int a,b; scanf("%d%d",&a,&b); add(b,a); sta[a]=true; } int root=1; while(sta[root]) root++; dfs(root); cout<<max(f[root][0],f[root][1])<<endl;
}
child chain on tree
Figure 2 Tree with negative weights
The longest diameter of a tree with negative weights
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=2e5+10;
const int INF=0x3f3f3f3f;
int ne[MAX],e[MAX],h[MAX],idx;
int n;
ll w[MAX],dp[MAX];
ll ans=-INF;
void add(int a,int b)
{ e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int pre)
{ dp[u]=w[u]; ans=max(ans,dp[u]); for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==pre)//Already visited continue; dfs(j,u); ans=max(ans,dp[j]+dp[u]);//Select the longest leaf chain dp[u]=max(dp[u],dp[j]+w[u]);//The longest leaf chain can continue to upload updated answers }
}
int main()
{ int n; cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; memset(h,-1,sizeof h); for(int i=0;i<n-1;i++) { int a,b; cin>>a>>b; add(a,b); add(b,a); } dfs(1,-1); cout<<ans<<endl;
}