Untitled

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define int long long
const int MAXN = 1000005;

typedef struct pair pair;
struct pair {
    int pri, end;
    pair *nxt;
};

typedef struct node node;
struct node {
    int val;
    node *nxt;
};

pair *price[MAXN];
node *graph[MAXN];
int inv[MAXN], child[MAXN], queue[MAXN], graph_len[MAXN], ttl[MAXN], child_done[MAXN];

void get_child(int now) {
    node *i = graph[now];
    while (i) {
        get_child(i->val);
        child[now] += child[i->val];
        i = i->nxt;
    }
    child[now]++;
}

int min(int a, int b) {
    if (a < b)
        return a;
    else
        return b;
}

int max(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

signed main() {
    int n, m, C;
    scanf("%lld %lld %lld", &n, &m, &C);
    for (int i = 2; i <= n; i++) {
        int x;
        scanf("%lld", &x);
        inv[i] = x;

        node *newNode = malloc(sizeof(node));
        newNode->val = i;
        newNode->nxt = graph[x];
        graph[x] = newNode;
        graph_len[x]++;
    }
    get_child(1);

    for (int t = 0; t < m; t++) {
        for (int i = 1; i <= n; i++) {
            pair *newNode = malloc(sizeof(pair));
            scanf("%lld %lld", &newNode->pri, &newNode->end);
            newNode->end += t;

            newNode->nxt = price[i];
            price[i] = newNode;
        }
        int head = 0, tail = 0;
        for (int i = 1; i <= n; i++)
            if (child[i] == 1) queue[tail++] = i;

        memset(child_done, 0, sizeof(child_done));
        memset(ttl, 0, sizeof(ttl));

        int ans = 0;
        while (head != tail) {
            int i = queue[head++];
            int miP = 1e9;
            for (pair *p = price[i]; p; p = p->nxt) {
                if (p->end >= t) miP = min(miP, p->pri);
            }
            ttl[i] += miP;
            if (ttl[i] <= C) ans = max(ans, child[i]);

            ttl[inv[i]] += ttl[i];
            if (++child_done[inv[i]] == graph_len[inv[i]] && ttl[inv[i]] <= C) queue[tail++] = inv[i];
        }
        printf("%lld\n", ans);
    }
}