Submission #19415770

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

vector<vector<int>> graph;
vector<int> x, y;

void DFS(int v){
    vector<int> dp(x[v]+1, INF);
    dp[0] = 0;

    for(auto child_v : graph[v]){
        DFS(child_v);
        vector<int> dp_new(x[v]+1, INF);
        for(int sum=0; sum<=x[v]; sum++){
            if(sum + x[child_v] <= x[v]) dp_new[sum + x[child_v]] = min(dp_new[sum + x[child_v]], dp[sum] + y[child_v]);
            if(sum + y[child_v] <= x[v]) dp_new[sum + y[child_v]] = min(dp_new[sum + y[child_v]], dp[sum] + x[child_v]);
        }
        dp = dp_new;
    }
    for(int sum=0; sum<=x[v]; sum++){
        y[v] = min(y[v], dp[sum]);
    }
}

int main(){
    int n;
    cin >> n;

    graph.resize(n);
    for(int i=1; i<n; i++){
        int p;
        cin >> p;

        p -= 1;
        graph[p].push_back(i);
    }

    x.resize(n);
    y.assign(n, INF);
    for(int i=0; i<n; i++){
        cin >> x[i];
    }

    DFS(0);
    if(y[0] == INF) cout << "IMPOSSIBLE" << endl;
    if(y[0] != INF) cout << "POSSIBLE" << endl;
    return 0;
}

Submission Info

Judge Result