【BZOJ】ARC083 E - 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.
 
소스/분류
ABC074&ARC083 
 
제목: 각 결점은 검은색이나 흰색으로 염색할 수 있으며, 각 결점의 자수와 자신의 동색의 자결점의 권한치를 합치면 v[x]와 같고, 여기는 자신을 포함한다.
너에게 실행 가능한 방안이 있느냐고 물었다.
사고방식: 이 문제는 인터넷의 많은 블로그를 보면 대충 알 수 있다. 여기서 나의 이해를 말하자면 모든 결점은 검은색이나 흰색으로 염색할 수 있다. 각 결점 x는 그의 서브트리에 있는 모든 동색 결점의 값과 같아야 한다. 여기 자체의 값은 임의로 클 수 있기 때문에 동색 서브 결점의 값이 그가 요구하는 v[x]보다 작다는 것을 보증하면 된다. 우리는 dfs를 이용하여 아래에서 위로 값을 되돌려준다.그렇다면 하나의 결점이 이미 검은색으로 물들었다고 가정하면 우리는 그의 모든 흰색 결점이 최소치로 전달될 수 있도록 보장해야 한다. 같은 이치로 만약에 흰색이라면 비교적 작은 검은색이 되돌아올 수 있다. 점마다 반드시 하나의 색깔이 있기 때문에 우리는 하나의 결점 X가 v[x] 범위 내에서 모든 결점을 통해 작은 값을 전달할 수 있다는 것을 보장하면 실행 가능한 상황을 설명한다. 그리고 이를 바탕으로배색 권한이 가장 적은 경우를 찾으면 됩니다. dp[i][j]는 하위 트리의 검은색 권한과 j인 경우 흰색 권한의 최소값을 고려하여 dp 초기값을 inf로 설정합니다.물론 이곳의 검은색과 흰색은 절대적인 것이 아니기 때문에 우리는 각 자결점의 배색 상황을 일일이 열거하면 된다. 처음에 왜 그의 코드에 X=1-X가 있는지 이해하지 못했는데 나중에 모든 자결점이 판단할 때 dp[X]를 한 번씩 똑똑히 보고 모든 값을 inf로 바꾸면 이전의 결점을 바탕으로 DP 조작을 할 수 있다. 만약에 어떤 결점의 v가 v보다 크다면 m는 것을 알게 된다.이렇게 전해진 모든 값이 inf라서 풀리지 않았다. 이렇게 전해진 것도 INF인데 자신이 너무 어리석어서 한참을 이해했다.
 
코드:
#include using namespace std; const int maxx=5005,maxn=1005,inf=0x3f3f3f3f;
int mi[maxn],dp[2][maxx]; int n; int first[maxn],tot,v[maxn];
struct edg{     int v,from; }e[maxn];
int read(){     char c;     int s=0,t=1;     while(!isdigit(c=getchar())) {         if(c=='-') t=-1;     }     do{
        s=s*10+c-'0';     }while(isdigit(c=getchar()));     return s*t; }
void insert(int u, int v) {///건변 tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void dfs(int x){     for(int i=first[x];i;i=e[i].from) dfs(e[i].v);     memset(dp[0],0x3f,sizeof(dp[0]));     int X=0;     dp[X][0]=0;     for(int i=first[x];i;i=e[i].from){         int y=e[i].v;         X=1-X;         memset(dp[X],0x3f,sizeof(dp[X]));         for(int j=0;j<=v[x];j++){             if(j-v[y]>=0) dp[X][j]=min(dp[X][j],dp[1-X][j-v[y]]+mi[y]);             if(j-mi[y]>=0) dp[X][j]=min(dp[X][j],dp[1-X][j-mi[y]]+v[y]);         }     }     for(int i=0;i<=v[x];i++) mi[x]=min(mi[x],dp[X][i]); } int main(){     n=read();     for(int i=2;i<=n;i++){         int p=read();         insert(p,i);     }
    for(int i=1;i<=n;i++) v[i]=read();     memset(mi,0x3f,sizeof(mi));     dfs(1);     if(mi[1]     else printf("IMPOSSIBLE"); }
 
참조 블로그:https://blog.csdn.net/Rising_shit/article/details/80849320(말을 참 잘하는데, 아쉽게도 나는 한참을 보았다.