// Задача AT4 — ДЖАНКИ
// Решение за подзадача 3 (дървото е път, w_j = 1).  Сложност: O(m log m).
//
// По линеен граф множество от обрани джанки е допустимо, когато дните им са
// ненарастващи надолу. Подреждаме джанките по връх и отговорът е дължината на най-
// дългата ненарастваща подредица на дните (= най-дълга ненамаляваща на отрицателните дни).

#include <vector>
#include <algorithm>

namespace {
const int MAXM = 100000 + 5;
int orderIdx[MAXM];
int tails[MAXM];
}

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 i = 0; i < m; i++) orderIdx[i] = i;
    std::sort(orderIdx, orderIdx + m, [&](int a, int b) {
        return fruitVertex[a] < fruitVertex[b];
    });

    int length = 0;
    for (int idx = 0; idx < m; idx++) {
        int negativeDay = -fruitDay[orderIdx[idx]];
        int pos = (int)(std::upper_bound(tails, tails + length, negativeDay) - tails);
        tails[pos] = negativeDay;
        if (pos == length) length++;
    }
    return (long long)length;
}
