Untitled

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define int long long
#define 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], Q[MAXN], graph_len[MAXN], ttl[MAXN], child_done[MAXN],Tail;

void get_child(int now) {
    for(node *i=graph[now];i;i=i->nxt){ 
        get_child(i->val);
        child[now] += child[i->val];
    }
    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 i = 1; i <= n; i++) if (child[i] == 1) Q[Tail++] = i;

    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;
            
            child_done[i] = ttl[i] = 0;
        }
        int head = 0, tail = 0;
        for (int i = 0; i < Tail; i++) queue[tail++] = Q[i];
        int ans = 0;
        while (head != tail) {
            int i = queue[head++];
            
            pair *p = price[i];
            int miP = p->pri;
            while(p->nxt){
                if(p->nxt->end < t) p->nxt=p->nxt->nxt;
                else{
                    p=p->nxt;
                    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);
    }
}