给出一棵有n个节点的无根树，给出\(w[x][y]\)表示x与y的边权，现在询问每个点的到达其他点的最长路径长度（显然不能选它自己）,\(n\leq 10000\)。
显然为树形递推题目，无根就钦定一个根，不妨为1,因为存在多个点的性质询问，考虑二次递推+换根法，于是设\(A[x]\)表示以x为节点的子树中，x的最长路径长度，不难有
\[A[x]=\max_{y\in son(x)}\{A[y]+w[x][y]\}\]
边界：叶结点为0
现在注意力放在换根上，设\(B[x]\)为x的最长路径长度，但是注意求\(B[y]\)的时候，如\(A[x]\)的最优解利用了y的话，那么就无法求出正确的结果，也许你会想去用一个次小值即可，但是你要维护次小值，可能又要次次小值，次次次小值，按ms的话说，就是没完没了了。
法一：
注意到y的最优解不能使用\(B[x]\)时，我们可以维护一个\(a[x][y]\)表示求A的最优解不讨论y的情况下的值，先把x的子节点的连上x的最优解分别处理出来，用st表即可维护\(a[x][y]\)，同理对B也设出这样一个东西，同理也可以维护出\(b[x][y]\)，这样就可以\(nlog(n)\)求出，但代码实现太复杂，常数太大，请读者自行实现。
法二：
换走维护的思路，注意到y这样的节点对于x来说只有一个，于是考虑暴力维护它，如图
假设\(B[x]\)的最优解在y中，那么y的最优解要考虑的只有\(A[y]\)，还有与x相连从上面来的路径（显然经过z），还有经过它兄弟的路径，不妨记经过z的从上面来到x的最大路径长度为czf，暴力临时维护y的兄弟w的最大值\(A[w]+l2\)表示经过y的兄弟的到x的最长路径长度，与czf取max，那么
\[B[y]=\max(czf+l3,A[y])\]
并记录一个\(pre[x]\)表示x的最优解是哪个节点，特别地为0意思是无需考虑，当
\(czf<A[y]\)时,\(pre[y]\)就为求出\(A[y]\)的最优节点，否则记为0.
至于y的兄弟w，有
\[B[w]=\max(A[w],B[x]+l2)\]
如果\(A[w]>B[x]+l2\),\(pre[w]\)就为求出\(A[w]\)的节点，否则为0.
因为这样的节点很少，所以时间复杂度为\(O(n)\)。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define ll long long
using namespace std;
struct point{
int next,to,w;
}ar[20050];
bool check[10015];
ll dp[10015],db[10015];
int at,head[10015],pre[10015];
void dfs1(int),dfs2(int,ll);
il void link(int,int,int);
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(dp,0,sizeof(dp));
at&=0,memset(head,0,sizeof(head));
for(int i(2),u,l;i<=n;++i)
scanf("%d%d",&u,&l),
link(i,u,l),link(u,i,l);
dfs1(1),dfs2(1,0);
for(int i(1);i<=n;++i)
printf("%lld\n",db[i]);
}
return 0;
}
void dfs2(int x,ll lsy){
check[x]&=0;ll czf(0);
for(ri int i(head[x]);i;i=ar[i].next)
if(check[ar[i].to]){
if(pre[x]==i)continue;
if(db[ar[i].to]<db[x]+ar[i].w)
db[ar[i].to]=db[x]+ar[i].w,pre[ar[i].to]=0;
czf=max(czf,dp[ar[i].to]+ar[i].w);
dfs2(ar[i].to,db[x]+ar[i].w);
}
if(pre[x]){
czf=max(lsy+ar[pre[x]].w,czf+ar[pre[x]].w);
if(db[ar[pre[x]].to]<czf)
db[ar[pre[x]].to]=czf,pre[ar[pre[x]].to]=0;
dfs2(ar[pre[x]].to,czf);
}
}
void dfs1(int x){
check[x]|=true;
for(int i(head[x]);i;i=ar[i].next){
if(check[ar[i].to])continue;dfs1(ar[i].to);
if(dp[ar[i].to]+ar[i].w>dp[x])
dp[x]=dp[ar[i].to]+ar[i].w,pre[x]=i;
}db[x]=dp[x];
}
il void link(int u,int v,int w){
ar[++at].to=v,ar[at].w=w;
ar[at].next=head[u],head[u]=at;
}
原文：https://www.cnblogs.com/a1b3c7d9/p/11007626.html