[动态规划][树形dp]Bichrome Tree

题目描述

We have a tree with N vertices. Vertex 1 is the root of the tree,and the parent of Vertex i (2≤i≤N) is Vertex Pi.
To each vertex in the tree,Snuke will allocate a color,either black or white,and a non-negative integer weight.
Snuke has a favorite integer sequence,X1,X2,…,XN,so he wants to allocate colors and weights so that the following condition is satisfied for all v.
The total weight of the vertices with the same color as v among the vertices contained in the subtree whose root is v,is Xv.
Here,the subtree whose root is v is the tree consisting of Vertex v and all of its descendants.
Determine whether it is possible to allocate colors and weights in this way.

Constraints
1≤N≤1 000
1≤Pi≤i?1
0≤Xi≤5 000

?

输入

Input is given from Standard Input in the following format:
N
P2 P3 … PN
X1 X2 … XN

?

输出

If it is possible to allocate colors and weights to the vertices so that the condition is satisfied,print POSSIBLE; otherwise,print IMPOSSIBLE.

?

样例输入

3
1 1
4 3 2

?

样例输出

POSSIBLE

?

提示

For example,the following allocation satisfies the condition:
Set the color of Vertex 1 to white and its weight to 2.
Set the color of Vertex 2 to black and its weight to 3.
Set the color of Vertex 3 to white and its weight to 2.
There are also other possible allocations.

思路：就是，对每一个节点i，在子树(包括i)中和它同色的权值和固定了，此时，要使子树中和它异色的权值和越小越好，这样以便给在其上方的节点更多选择的余地，所以用状态dp[i]，表示i节点的子树中和它异色的最小权值和是多少，其实也就是求i节点的子树(不包括i)中和它同色的不超过w[i]的最大权值和tmp，那么dp[i]=sum-tmp;

(其中sum=

,j为i的直接子节点)

AC代码：

#include <iostream>
#include<cstdio>
#include<vector>
#define inf 0x3f3f3f3f
using namespace std;

vector<int> sons[1010];
int w[1010],dp[1010];
int tmp[1010][5050];
bool ok=true;

void dfs(int x){
  int sum=0;
  for(int i=0;i<(int)sons[x].size();i++) dfs(sons[x][i]);
  if(!ok) return;//在ok已经是false的状态下，不要再进行tmp的计算了，否则会导致sum爆int，引起一系列问题，比如RE
  for(int i=0;i<(int)sons[x].size();i++){
    int son=sons[x][i];
    sum+=(w[son]+dp[son]);
    for(int j=0;j<=w[x];j++){
        tmp[i+1][j]=-inf;
        //tmp的状态转移方程
        if(j>=w[son]) tmp[i+1][j]=max(tmp[i+1][j],tmp[i][j-w[son]]+w[son]);
        if(j>=dp[son]) tmp[i+1][j]=max(tmp[i+1][j],tmp[i][j-dp[son]]+dp[son]);
    }
  }
  if(tmp[sons[x].size()][w[x]]<0) ok=false,dp[x]=inf;
  else dp[x]=sum-tmp[sons[x].size()][w[x]];
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=2;i<=n;i++){
        int p;scanf("%d",&p);
        sons[p].push_back(i);
    }
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    dfs(1);
    if(ok) printf("POSSIBLEn");
    else printf("IMPOSSIBLEn");
    return 0;
}

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!