紫书动规 P282的问题 hdu2196 树形dp

题目链接:

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

题意:

题解:

http://blog.csdn.net/shuangde800/article/details/9732825
f[i][0],表示顶点为i的子树的，距顶点i的最长距离
f[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离

要求所有的f[i][0]很简单，只要先做一次dfs求每个结点到叶子结点的最长距离即可。
然后要求f[i][1], 可以从父节点递推到子节点，

代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 1e5+10;
 17 
 18 struct node{
 19     int v,w;
 20 };
 21 vector<node> g[maxn];
 22 int vis[maxn],f[maxn][2];
 23 
 24 int dfs1(int u){
 25     vis[u] = 1;
 26     f[u][0] = 0;
 27     for(int i=0; i<(int)g[u].size(); i++){
 28         int v = g[u][i].v, w = g[u][i].w;
 29         if(vis[v]) continue;
 30         f[u][0] = max(f[u][0],dfs1(v)+w);
 31     }
 32     return f[u][0];
 33 }
 34 
 35 
 36 
 37 void dfs2(int u){
 38     vis[u] = 1;
 39     int max1=0,max2=0,v1,v2;
 40 
 41     for(int i=0; i<(int)g[u].size(); i++){
 42         int v = g[u][i].v, w = g[u][i].w;
 43         if(vis[v]) continue; // 不能返回到父节点
 44 
 45         int tmp = f[v][0]+w;
 46         if(tmp > max1){
 47             max2 = max1; v2 = v1;
 48             max1 = tmp; v1 = v;
 49         }else if(tmp > max2){
 50             max2 = tmp; v2 = v;
 51         }
 52     }
 53 
 54     if(u != 1){
 55         int tmp = f[u][1];
 56         int v = -1;
 57         if(tmp > max1){
 58             max2 = max1; v2 = v1;
 59             max1 = tmp; v1 = v;
 60         }else if(tmp > max2){
 61             max2 = tmp; v2 = v;
 62         }
 63     }
 64 
 65     for(int i=0; i<(int)g[u].size(); i++){
 66         int v = g[u][i].v, w = g[u][i].w;
 67         if(vis[v]) continue;
 68         if(v == v1)
 69             f[v][1] = max2 + w;
 70         else
 71             f[v][1] = max1 + w;
 72         // cout << v << " " << f[v][1] << endl;
 73         dfs2(v);
 74     }
 75 
 76 }
 77 
 78 int main(){
 79     int n;
 80     while(scanf("%d",&n) == 1){
 81         for(int i=0; i<=n; i++) g[i].clear();
 82         for(int i=2; i<=n; i++){
 83             int v,w; cin >> v >> w;
 84             g[i].push_back(node{v,w});
 85             g[v].push_back(node{i,w});
 86         }
 87         MS(f);
 88         MS(vis);
 89         dfs1(1);
 90         MS(vis);
 91         dfs2(1);
 92 
 93         for(int i=1; i<=n; i++)
 94             cout << max(f[i][0],f[i][1]) << endl;
 95     }
 96 
 97 
 98 
 99     return 0;
100 }