题意 :给定一张图,问图中的每个节点可到达叶子节点的最远距离
分析可知,对于一个节点的最远距离来说,把该点作为树的根节点来考虑,那么最远距离要么是从该节点往下走,要么是从该节点往上走,再往下走。
对于后一种情况来说,还要保证往下走的时候不会再一次经过该节点,所以要记录一个次远距离,当这种情况发生的时候,就用这个次远距离来计算。
因为 N = 10000,那么就考虑用dp来做。
down[i]为该节点往下走的最远距离
roll[i]为从该节点往上走再往下走的最远距离
second[i]为该节点往下走的次远距离
num_long[i]记录这个节点的最远距离是由哪个节点得出的
可以推出状态转移方程:
down[now]=max(down[now],down[son]+w);
and
roll[son]=max(roll[now],down[now])+w;
or roll[son]=max(roll[now],second[now])+w;
通过两次dfs()来得出结果
#include<stdio.h> #include<iostream> #include<string> #include<stdlib.h> #include<string.h> #include<math.h> #include<queue> #include<vector> using namespace std; const int maxn = 10005; int max(int a,int b){ return a>b?a:b; } struct node{ int num,w; }; int down[maxn]; int roll[maxn]; int second[maxn]; int num_long[maxn]; vector<node>tree[maxn]; int dfs1(int now){ if( down[now] ) return down[now]; int Size = tree[now].size(); if( !Size) return 0; int flag = 0; for(int i = 0; i < Size; i ++){ int next = tree[now][i].num; if( dfs1(next) + tree[now][i].w > down[now] ){ second[now] = down[now]; down[now] = down[next] + tree[now][i].w; flag = next; } else if( down[next] + tree[now][i].w > second[now] ) second[now] = down[next] + tree[now][i].w; } num_long[now] = flag; return down[now]; } void dfs2(int now){ int Size = tree[now].size(); for(int i = 0; i < Size; i ++){ int next = tree[now][i].num; if( num_long[now] == next){ roll[next] = max( roll[now], second[now] ) + tree[now][i].w; } else roll[next] = max( roll[now], down[now] ) + tree[now][i].w; dfs2(next); } } int main(){ int n; while(scanf("%d",&n)!=EOF){ int i; memset(down,0,sizeof(down)); memset(roll,0,sizeof(roll)); memset(second,0,sizeof(second)); memset(num_long,0,sizeof(num_long)); for(i=0;i<=n;i++) tree[i].clear(); for(i=2;i<=n;i++){ int a,b; scanf("%d%d",&a,&b); node t; t.num=i; t.w=b; tree[a].push_back(t); } dfs1(1); dfs2(1); for(i=1;i<=n;i++){ printf("%d\n", max( roll[i],down[i] ) ); } } return 0; }