HDU 2196 Computer 树形DP 经典题

给出一棵树，边有权值，求出离每一个节点最远的点的距离

树形DP，经典题

本来这道题是无根树，可以随意选择root，

但是根据输入数据的方式，选择root=1明显可以方便很多。

我们先把边权转化为点权，放在数组cost中

令tree(i)表示以节点i为根的子树

对于节点i，离该节点最远的点要不就是在tree(i)中，要不就是在father(i)上面

令：

dp[i][1] : 在子树tree(i)中，离i最远的距离

dp[i][2] : 在子树tree(i)中，离i第二远的距离 (递推的时候需要)

dp[i][0] : 在树tree(root)-tree(i)中，离i最远的距离

son[i] : 在子树tree(i)中，离i最远的点是在tree(son[i])中，即最远路径经过节点son[i]

则对于每一个i，离i最远的距离=max(dp[i][0],dp[i][1])

流程：

0.链式前向星建树

1.dfs1，确定dp[i][1]

2.dfs2，确定dp[i][2]

dfs1和dfs2都很简单

3.dfs3，递推确定dp[i][0]

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn=+;

 const int inf=0x3f3f3f3f;

 inline int max(int a,int b)

 {

     return a>b?a:b;

 }

 struct Edge

 {

     int to,next;

 };

 Edge edge[maxn];

 int head[maxn];

 int tot;

 int cost[maxn];

 int son[maxn];

 int dp[maxn][];

 void init()

 {

     memset(head,-,sizeof head);

     tot=;

     memset(dp,,sizeof dp);

     memset(son,-,sizeof son);

 }

 void addedge(int u,int v)

 {

     edge[tot].to=v;

     edge[tot].next=head[u];

     head[u]=tot++;

 }

 void solve(int n);

 void dfs1(int u,int pre);

 void dfs2(int u,int pre);

 void dfs3(int u,int pre);

 int main()

 {

     int n;

     while(~scanf("%d",&n))

     {

         init();

         cost[]=;

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

         {

             int u;

             scanf("%d %d",&u,&cost[i]);

             addedge(u,i);

         }

         solve(n);

     }

     return ;

 }

 void solve(int n)

 {

     dfs1(,-);

     dfs2(,-);

     dp[][]=;

     dfs3(,-);

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

     {

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

     }

     return ;

 }

 void dfs1(int u,int pre)

 {

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         dfs1(v,u);

         if(dp[v][]+cost[v]>dp[u][])

         {

             dp[u][]=dp[v][]+cost[v];

             son[u]=v;

         }

     }

 }

 void dfs2(int u,int pre)

 {

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         dfs2(v,u);

         if(v==son[u])

             continue;

         if(dp[v][]+cost[v]>dp[u][])

             dp[u][]=dp[v][]+cost[v];

     }

 }

 void dfs3(int u,int pre)

 {

     for(int i=head[u];~i;i=edge[i].next)

     {

         int v=edge[i].to;

         if(v==son[u])

         {

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

         }

         else

         {

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

         }

         dfs3(v,u);

     }

 }

巴特西

HDU 2196 Computer 树形DP 经典题

最新文章

热门文章