// Задача AT4 — ДЖАНКИ
// Решение за подзадача 8 (без ограничения).  Сложност: O(n log^2 n).
//
// За всеки връх v разглеждаме функцията f(v, t) = максималният брой добре узрели
// джанки, които можем да приберем от поддървото на v, ако всички срязвания в него
// стават в дни <= t.  Тази функция е ненамаляваща стъпаловидна по t, затова я пазим
// компактно като асоциативен масив „ден -> с колко нараства f точно на този ден“.
//
// Функцията на връх е сумата от функциите на децата плюс приноса на джанките в самия
// връх.  Сумата на стъпаловидни функции = обединение на масивите със събиране по общи
// ключове; правим я по схемата „малко към голямо“ (вливаме по-малкия масив в по-големия).
// Джанките (с ден d и брой w) добавят +w в ден d, след което „поглъщат“ толкова от
// по-късните нараствания, колкото е w — така пазим горната обвивка: печалбата се
// реализира само ако срязваме в ден >= d, измествайки по-късни, но по-слаби възможности.

#include <vector>
#include <map>
#include <algorithm>

long long solve(int n, int m, int k,
                const std::vector<int>& parent,
                const std::vector<int>& fruitVertex,
                const std::vector<int>& fruitDay,
                const std::vector<long long>& fruitCount) {
    // Списък с децата на всеки връх (връх i+2 има родител parent[i]).
    std::vector<std::vector<int>> children(n + 1);
    for (int i = 0; i < n - 1; i++) {
        children[parent[i]].push_back(i + 2);
    }

    // Ден и брой джанки за всеки връх (0, ако във върха няма джанки).
    std::vector<int> ripeDay(n + 1, 0);
    std::vector<long long> ripeCount(n + 1, 0);
    for (int j = 0; j < m; j++) {
        ripeDay[fruitVertex[j]] = fruitDay[j];
        ripeCount[fruitVertex[j]] = fruitCount[j];
    }

    // Обхождаме върховете в ред, в който всяко дете идва преди родителя си.
    std::vector<int> postOrder;
    postOrder.reserve(n);
    std::vector<int> stack = {1};
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        postOrder.push_back(u);
        for (int child : children[u]) {
            stack.push_back(child);
        }
    }

    // step[u] = функцията f(u, .), представена като ден -> нарастване.
    std::vector<std::map<int, long long>*> step(n + 1, nullptr);

    for (int i = n - 1; i >= 0; i--) {
        int u = postOrder[i];

        // Сливаме функциите на децата по схемата „малко към голямо“.
        std::map<int, long long>* current = nullptr;
        for (int child : children[u]) {
            if (current == nullptr) {
                current = step[child];
            } else {
                if (current->size() < step[child]->size()) {
                    std::swap(current, step[child]);
                }
                for (const auto& entry : *step[child]) {
                    (*current)[entry.first] += entry.second;
                }
                delete step[child];
            }
            step[child] = nullptr;
        }
        if (current == nullptr) {
            current = new std::map<int, long long>();
        }

        // Добавяме джанките на върха и поглъщаме по-късните, по-слаби нараствания.
        if (ripeDay[u] != 0) {
            long long remaining = ripeCount[u];
            (*current)[ripeDay[u]] += remaining;
            auto it = current->upper_bound(ripeDay[u]);
            while (it != current->end() && remaining > 0) {
                if (it->second <= remaining) {
                    remaining -= it->second;
                    it = current->erase(it);
                } else {
                    it->second -= remaining;
                    remaining = 0;
                }
            }
        }

        step[u] = current;
    }

    // Отговорът е пълната стойност на f в корена = сумата на всички нараствания.
    long long answer = 0;
    for (const auto& entry : *step[1]) {
        answer += entry.second;
    }
    delete step[1];
    return answer;
}
