部分木単位で同じ問題を解けないかを考えると、ある頂点 \(i\) についてその子 \(c\) は \((i,c)\) 間の辺を選ぶか選ばないかの二通りあることがわかります。そこから以下の動的計画法を考えます

\(\text{dp}[v][0/1]=\) 頂点 \(v\) を根とする部分木について \(v\) の親への辺を (\(0\) : 担当しない \(1\) : 担当する) ときの部分木における追加コストの合計の最小値

このとき、答えは \((N-1)+\text{dp}[1][0]\) となります。

実際の遷移を考えます。\(\text{dp}[v]\) を求めるとき、その子 \(c_1,c_2,\ldots,c_k\) について \(\text{dp}[c_i]\) は全て求まっているとしたいです。よって、葉から順に \(\text{dp}\) をもとめていくとします。

子のうち、\((c_i,v)\) の辺を担当する子の集合を \(S\) と決め打ったとする、また \(U\) を\(v\) の子全体の集合とする。このとき、部分木のコストは \(\sum_{i \in S} \text{dp}[i][1] + \sum_{i \in U\setminus S} \text{dp}[i][0] + \max(0,|U\setminus S|-C_v)\times W_v\) です。 これは \(\text{dp}[v][0]\) を求める時の値で、\(\text{dp}[v][1]\) を求めるときは \(|U\setminus S|-C_v\) が \(|U\setminus S|-C_v+1\) となります。

ここで、すべての \(S\) を探索せずとも \(\text{dp}\) を更新することを考えます。\(S\) の大きさごとに、\(\sum_{i \in S} \text{dp}[i][1] + \sum_{i \in U\setminus S} \text{dp}[i][0] \) を最小化するような \(S\) を求めます。このとき、\(\text{dp}[c_i][1]-\text{dp}[c_i][0]\) が小さい順に \(S\) に追加していく貪欲法が正当になります。

したがって、この\(\text{dp}\) は全体で \(\mathrm{O}(N \log N)\) で求めることができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    vector<int> p(n, -1);
    for (int i = 1; i < n; ++i) cin >> p[i];
    for (int i = 1; i < n; ++i) p[i]--;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) g[p[i]].emplace_back(i);
    vector<ll> c(n), w(n);
    for (int i = 0; i < n; ++i) cin >> c[i] >> w[i];
    vector<array<ll, 2>> dp(n, array<ll, 2>{(ll)1e18, (ll)1e18});
    for (int i = n - 1; i >= 0; --i) {
        ll sum = 0;
        vector<ll> vec;
        for (auto u : g[i]) {
            sum += dp[u][0];
            vec.emplace_back(dp[u][1] - dp[u][0]);
        }
        sort(vec.begin(), vec.end());
        {
            int now = vec.size();
            dp[i][0] = w[i] * max(0LL, now - c[i]) + sum;
            dp[i][1] = w[i] * max(0LL, now + 1 - c[i]) + sum;
            ll tmp = 0;
            for (int j = 0; j < (int)vec.size(); ++j) {
                now--;
                tmp += vec[j];
                dp[i][0] = min(dp[i][0], w[i] * max(0LL, now - c[i]) + sum + tmp);
                dp[i][1] = min(dp[i][1], w[i] * max(0LL, now + 1 - c[i]) + sum + tmp);
            }
        }
    }
    cout << dp[0][0] + (n - 1) << endl;
}