从树的直径角度考虑
$O(n)$
1.若边权值均大于0
,直接使用树的直径解法,从任意一点出发找到当前距离最远的点,再从该点出发寻找最远距离即可。
2.考虑负权边,定义dist[i]
表示当前枚举点最后以i
号点结尾的最远距离,则最远距离为max(dist[父节点]+w[i],w[i])
。
3.结合前两者则可找到整棵树的最长路径,类似LIS
,最后答案落在max(dist[1....n])
。
4.由于操作均在树的链上,凭感觉yy的做法ac了,证明略有缺陷,欢迎讨论。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
#define int long long
int h[N],e[N<<1],ne[N<<1],w[N<<1],idx;
int n;
int dist[N];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int f,int x){
dist[u]=x;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j!=f) dfs(j,u,max(x+w[i],w[i]));
}
}
signed main(){
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
dfs(1,-1,0);
int u=1;
for(int i=2;i<=n;i++)
if(dist[i]>dist[u])
u=i;
dfs(u,-1,0);
cout<<*max_element(dist+1,dist+n+1);
}