题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2196

解题思路

化无根树为有根树进行分析：

蓝色区域为以2为根的子树，红色区域为以2的父亲结点1为根的（子）树，不包含以2为根子树的部分。
我们定义：
dp[i][0]表示节点i与以i为根的子树内最远的叶子节点之间的距离；
dp[i][1]表示节点i与非子树内最远的叶子节点之间的距离。
disMAX[i]的含义与dp[i][0]一致；
disMIN表示以i为根节点的子树内，节点i与次最远叶子节点之间的距离。

dp[i][0]比较好求，只要先dfs到底，在递归刷新每个节点的最大距离即可。
而求dp[i][1]则需要边dfs边刷新dp[i][1]。
假设节点u有n个子节点，分别是v1,v2…vn
那么
如果vi不是u最长距离经过的节点，dp[vi][1] = cost(vi,u)+max(disMAX[u], dp[u][1])；
如果vi是u最长距离经过的节点，那么不能选择f[u][0],因为这保存的就是最长距离，要选择以u为根子树的次最大距离，可得dp[vi][1] = cost(vi, u) + max(disMIN[u], dp[u][1])；

细节在代码中体现。

AC代码

#include<bits/stdc++.h>
#define pb push_back
#define ll long long 
using namespace std;
const int N=1e5+100;
struct computer
{int to,cost;//to表示与i相连的节点，cost表示二者的边权
};
int n,to,cost;
ll dp[N][2],disMAX[N],disMIN[N],pathMAX[N];//dp，disMAX，disMIN含义如上，pathMAX[i]=j表示以i为根节点的最长路径的儿子节点为j。
vector<computer> g[N];
void dfs1(int x,int fa)//求disMAX（即dp[][0]），和disMIN，以及保存路径
{for(int i=0;i<g[x].size();i++){if(g[x][i].to==fa) continue;//又回去了必然不行dfs1(g[x][i].to,x);//先dfs到底ll dis=disMAX[g[x][i].to]+g[x][i].cost;if(dis>disMAX[x])//判断是否要刷新最大距离，刷新{disMIN[x]=disMAX[x];//把原最大距离给次最大距离disMAX[x]=dis;//更新最大距离dp[x][0]=disMAX[x];//disMAX与dp[][0]同步刷新pathMAX[x]=g[x][i].to;//保存最大距离路径} else if(dis>disMIN[x]) disMIN[x]=dis;//不刷新最大距离，判断一下是否刷新次最大距离}
}
void dfs2(int x,int fa){//求dp[][1]for(int i=0;i<g[x].size();i++){if(g[x][i].to==fa) continue;if(pathMAX[x]!=g[x][i].to) //此点不在最大路径上{dp[g[x][i].to][1]=max(disMAX[x],dp[x][1])+g[x][i].cost;//对应上面的情况。}else//在最大路径上{dp[g[x][i].to][1]=max(disMIN[x],dp[x][1])+g[x][i].cost;//对应上面的情况}dfs2(g[x][i].to,x);//边dfs边赋值}
}
int main()
{while(cin>>n){//每次的初始化不可缺少memset(dp,0,sizeof dp);memset(disMAX,0,sizeof disMAX);memset(disMIN,0,sizeof disMIN);memset(pathMAX,0,sizeof pathMAX);for(int i=1;i<=n;i++) g[i].clear();//存图（树）for(int i=2;i<=n;i++){computer tmp;cin>>to>>cost;tmp.to=to,tmp.cost=cost;g[i].pb(tmp);tmp.to=i;g[to].pb(tmp);}dfs1(1,-1);dfs2(1,-1);for(int i=1;i<=n;i++)cout<<max(dp[i][0],dp[i][1])<<endl;}
}

参考资料

https://www.cnblogs.com/acgoto/p/9607627.html
https://blog.csdn.net/shuangde800/article/details/9732825