// Задача AT4 — ДЖАНКИ
// Решение за подзадача 5 (k <= 20, w_j = 1).  Същата директна O(n*k) динамика по
// поддървета както за подзадача 1, но при по-голям брой върхове n.
//
// f[v][t] = максималният брой добре узрели джанки от поддървото на v при срязвания в
// дни <= t. Понеже родителят винаги има по-малък номер от детето, обхождаме върховете
// в намаляващ ред: щом приключим връх v, добавяме функцията му към тази на родителя.

#include <vector>
#include <algorithm>

namespace {
const int MAXN = 100000 + 5;
const int MAXK = 21;
long long f[MAXN][MAXK];
int ripeDay[MAXN];
long long ripeCount[MAXN];
}

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) {
    for (int v = 1; v <= n; v++) {
        ripeDay[v] = 0;
        ripeCount[v] = 0;
        for (int t = 0; t <= k; t++) f[v][t] = 0;
    }
    for (int j = 0; j < m; j++) {
        ripeDay[fruitVertex[j]] = fruitDay[j];
        ripeCount[fruitVertex[j]] = fruitCount[j];
    }

    for (int v = n; v >= 1; v--) {
        // f[v] вече съдържа сбора по децата (добавен, когато те бяха обработени)
        if (ripeDay[v] != 0) f[v][ripeDay[v]] += ripeCount[v];
        for (int t = 1; t <= k; t++) f[v][t] = std::max(f[v][t], f[v][t - 1]);
        if (v >= 2) {
            int par = parent[v - 2];
            for (int t = 0; t <= k; t++) f[par][t] += f[v][t];
        }
    }
    return f[1][k];
}
