hdu 2196【树形dp】

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

题意：找出树中每个节点到其它点的最远距离。

题解：

　　首先这是一棵树，对于节点v来说，它到达其它点的最远距离可以走两个方向，一个是向它的子节点走，不妨称作正向走；一个是向它的父节点方向，不妨称作反向走。也就是说节点v能到达的最远距离是max{正向走的最远距离，反向走的最远距离}。所以可以先dfs一次求出每个节点能正向走的最大距离。显然反向走一定会经过父节点，这时就会出现两种情况：1.父节点u正向走的最远距离经过子节点v。2.父节点u走的最远距离不经过子节点v。当经过子节点v时，显然要算v反向走的最远距离时不能走u的正向最远的那条经过自己的路径，而u的正向第二远的路径将是最优的选择。可以想想看，v反向最远当然是由u的正向最远转移过来的，这个正向最远经不经过v很关键。因此正向dfs时还要记录一个第二最远的距离。

　　设dp[][3],dp[v][0]表示v正向走的最远距离，dp[v][1]表示v正向走的第二最远距离，dp[v][2]表示v反向走的最远距离。

　　那么答案显然是：ans=max{dp[v][0],dp[v][2]}。

　　其中:当u最远不经过v时：dp[v][2]=max{dp[u][2],dp[u][0]}+cost;

　　　　当u最远经过v时：dp[v][2]=max{dp[u][2],dp[u][1]}+cost;

　　我之前有个非常疑惑的地方就是为什么dp[v][2]的转移还要有dp[u][2]？我直接根据u经不经过v分两种情况不就是dp[v][2]了吗，怎么还要跟dp[u][2]+cost之间取个最大值？后来想想才明白，其实这也是个状态转移啊！dp[u][2]表示u反向走的最远距离，而dp[u][0],dp[u][1]都是正向走的距离，当由u推v的时候当然要从u的正向和反向之间取个最大值了！

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int MAXN=;

 struct Node{

     int to,cost;

 };

 vector<Node> tree[MAXN];

 int dp[MAXN][];

 int N;

 void init()

 {

     memset(dp,,sizeof(dp));

     for(int i=;i<=N;i++)

         tree[i].clear();

 }

 void dfs1(int u,int fa)

 {

     int FirstMax=,SecondMax=;

     for(int i=;i<tree[u].size();i++){

         int v=tree[u][i].to;

         int c=tree[u][i].cost;

         if(v==fa) continue;

         dfs1(v,u);

         if(dp[v][]+c>FirstMax){

             SecondMax=FirstMax;

             FirstMax=dp[v][]+c;

         }else if(dp[v][]+c>SecondMax)

             SecondMax=dp[v][]+c;

     }

     dp[u][]=FirstMax;

     dp[u][]=SecondMax;

 }

 void dfs2(int u,int fa)

 {

     int t;

     for(int i=;i<tree[u].size();i++){

         int v=tree[u][i].to;

         int c=tree[u][i].cost;

         if(v==fa) continue;

         if(dp[u][]==dp[v][]+c)

             t=dp[u][];

         else t=dp[u][];

         dp[v][]=max(dp[u][],t)+c;

         dfs2(v,u);

     }

 }

 int main()

 {

     while(scanf("%d",&N)==)

     {

         init();

         int a,b;

         Node n1;

         for(int i=;i<=N;i++){

             scanf("%d%d",&a,&b);

             n1.to=a,n1.cost=b;

             tree[i].push_back(n1);

             n1.to=i;

             tree[a].push_back(n1);

         }

         dfs1(,);

         dfs2(,);

         for(int i=;i<=N;i++)

             printf("%d\n",max(dp[i][],dp[i][]));

     }

     return ;

 }

巴特西

hdu 2196【树形dp】

最新文章

热门文章