NO IMAGE

連結 : 傳送門

題意: 給你一個n個節點的棵樹,然後給你和 第i臺電腦與第a臺電腦相連的花費 v 問你最長的線路是多長(求樹上任意節點所能達到的最遠點的距離)

樹形dp ,開個陣列 分別記錄這個點到子樹最遠節點的最長距離次長距離 和記錄到父節點上的最長距離 這樣在樹上dp
1. 求子樹最長次長
       dp[u][0] =max(dp[u][0],dfs(v,u) val) 子樹最長距離 =max(子樹節點到子樹的子樹的最遠距離 子樹到根的距離 , 子樹最長距離);
   a. 最長更新
      dp[u][1] =max(dp[u][1],dp[u][0])
   b. 最長不更新
    dp[u][1]=max(dp[u][1],dfs(v,u) val)
2.求父節點 最長
  a. 如果父節點最長子樹通過該節點,則父節點最長等於父節點次長加到子節點的距離或者父節點在其父節點的最長加到子節點的距離
    dp[v][2]=max(dp[u][2] val,dp[u][1] val)
  b. 如果不通過那就是父節點最長等於父節點最長加到子節點的距離或者父節點在其父節點的最長加到子節點的距離
    dp[v][2]=max(dp[u][2] val,dp[u][0] val)

#include<bits/stdc  .h>
using namespace std;
#define ll long long
#define rd(a) scanf("%d",&a)
#define rlld(a) scanf("%lld",&a)
#define me(a,b) memset(a,b,sizeof(a))
const int inf= 0x3f3f3f3f;
const int maxn=1e4   3;
const ll mod =1e9 7;
int dist[maxn][3];
struct node{
int next,v,val;
}ss[maxn*2];
int head[maxn];
int pre[maxn];
int cnt=0;
inline void add(int u,int v,int val){
ss[cnt].v=v;
ss[cnt].val=val;
ss[cnt].next=head[u];
head[u]=cnt  ;
}
inline void init (){
cnt=0;
me(head,-1);
me(dist,0);
me(pre,-1);
}
int dfs(int u,int fa)
{
for(int i=head[u];~i;i=ss[i].next){
int v=ss[i].v;
int val=ss[i].val;
if(v==fa) continue;
int ans=dfs(v,u);   
if(ans val>=dist[u][0]){
dist[u][1]=max(dist[u][0],dist[u][1]);
dist[u][0]=ans val;
pre[u]=v;
}
else{
dist[u][1]=max(dist[u][1],ans val);
}
}
return dist[u][0];
}
void dfs1(int u,int fa){
for(int i=head[u];~i;i=ss[i].next){
int v=ss[i].v;
int val=ss[i].val;
if(v==fa) continue;
if(pre[u]==v) dist[v][2]=max(dist[u][2] val,dist[u][1] val); 
else dist[v][2]=max(dist[u][0] val,dist[u][2] val);
dfs1(v,u);
}
}
int main(){
int n;
while(cin>>n){
init();
for(int i=2;i<=n;i  ) 
{
int v,val;
cin>>v>>val;
add(v,i,val);
add(i,v,val);
}
dfs(1,-1);
dfs1(1,-1);
for(int i=1;i<=n;i  ) cout<< max(dist[i][0],dist[i][2])<<endl;
}
return 0;
}