Untitled

mail@pastecode.io avatar
unknown
c_cpp
8 months ago
1.4 kB
4
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
const int MAXN = 1000005;

vector<int> graph[MAXN];
int inv[MAXN], child[MAXN];
priority_queue<pii, vector<pii>, greater<pii>> pq[MAXN];

void get_child(int now) {
    for (auto i : graph[now]) {
        get_child(i);
        child[now] += child[i];
    }
    child[now]++;
}

signed main() {
    int n, m, C;
    cin >> n >> m >> C;
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        graph[x].pb(i);
        inv[i] = x;
    }

    get_child(1);
    queue<int> Q;
    for (int i = 1; i <= n; i++) if (child[i] == 1) Q.push(i);

    for (int t = 0; t < m; t++) {
        vector<pii> price(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> price[i].F >> price[i].S, price[i].S += t;
            pq[i].push(price[i]);
            while (pq[i].top().S < t) pq[i].pop();
        }

        queue<int> q(Q);
        vector<int> child_done(n + 1), ttl(n + 1);
        int ans = 0;
        while (!q.empty()) {
            int i = q.front();
            q.pop();

            ttl[i] += pq[i].top().F;
            if (ttl[i] <= C) ans = max(ans, child[i]);
            
            ttl[inv[i]] += ttl[i];
            if (++child_done[inv[i]] == graph[inv[i]].size() && ttl[inv[i]] <= C) q.push(inv[i]);
        }
        cout << ans << '\n';
    }
}