hdu2196 树形DP

题意:
      给你一棵树,求出每一个点到其他点的最大距离.

思路:

      每个点的最大距离只有两种情况,1是自己忘下面走的最大,二是网上走的最大,取他们的最大便是答案,每个点网下面的最大可以空过dfs直接在回溯的时候求出来,但网上走的呢?往上走其实就是他父亲往上走的最大 和 他父亲往下走最大 中大的那个加上他和她父亲的距离得到的,但是他父亲往下走的最大有可能是他这条路,就是路过他,那么怎么办呢,我们可以再第一遍dfs求最大的时候求出个次大,第二大,当最大的路路过他时那么直接用次大的代替最大,就这样树形dp一边,得到自己网上走的最大,然后输出自己网上走最大和往下走最大中的最优值就行了,具体看代码就懂了,第一遍深搜从下网上,第二遍从上往下...据说还可以用树的直径的性质做,求出树的直径,然后输出max(dis[s] ,dis[t]);自己没试验行不行,不知道时间能不能超时,如果超时我感觉可以用LCA去优化...

#include<stdio.h>
#include<string.h>

#define N 11000
                                     
typedef struct
{
   int to ,next ,cost;
}STAR;

STAR E[N];

int list[N] ,tot;
int maxz[N] ,maxc[N];
int dp[N] ,mer[N];

void add(int a ,int b ,int c)
{
   E[++tot].to = b;
   E[tot].cost = c;
   E[tot].next = list[a];
   list[a] = tot;
}

int maxx(int a ,int b)
{          
   return a > b ? a : b;
}

void DFS1(int s)
{
   int maz = 0 ,mac = 0 ,mk = 0;
   for(int k = list[s] ;k ;k = E[k].next)
   {
      int to = E[k].to;
      mk =  1;
      DFS1(to);
      if(maz <  maxz[to] + E[k].cost)
      {                        
         mer[s] = to;
         mac = maz;
         maz = maxz[to] + E[k].cost;
      } 
      else
      mac = maxx(mac ,maxz[to] + E[k].cost);
   }
   if(mk)
   {
      maxz[s] = maz;
      maxc[s] = mac;
   }
   else maxz[s] = maxc[s] = 0;
}

void DFS2(int s)
{
   for(int k = list[s] ;k ; k = E[k].next)
   {
      int to = E[k].to;
      if(to == mer[s])
      dp[to] = maxx(dp[s] ,maxc[s]) + E[k].cost;
      else
      dp[to] = maxx(dp[s] ,maxz[s]) + E[k].cost;
      DFS2(to);
   }
}

int main ()
{
   int  n ,i ,a ,b;
   while(~scanf("%d" ,&n))
   {
      memset(list ,0 ,sizeof(list));
      tot = 1;
      for(i = 2 ;i <= n ;i ++)
      {
         scanf("%d %d" ,&a ,&b);
         add(a ,i ,b);
      }
      DFS1(1);
      dp[1] = 0;
      DFS2(1);
      
      for(i = 1 ;i <= n ;i ++)
      printf("%d
" ,maxx(maxz[i] ,dp[i]));
   }
   return 0;
}