题目描述

萨什卡有一棵由 $N$ 个顶点构成的樱桃李树。顶点 $1$ 位于树的最上方，并被定义为根。

除根以外，每个顶点最多生长一簇樱桃李。对于第 $j$ 簇果实，给定：

• 它所在的顶点 $V_j$；
• 它恰好成熟的日期 $D_j$；
• 若在该日采下，可得到的果实数量 $W_j$。

萨什卡只能通过砍断树枝来采摘。

在任意一天，她可以同时砍断任意多条边。树会因此分裂成若干连通块，所有不再与根相连的部分都会掉落到地面。

对于每个掉落部分，她只会收获在当天恰好成熟的果实：

• 尚未成熟就掉落的果实会浪费；
• 一直留在树上直到过熟的果实也会浪费。

形式化地说，每天萨什卡可以删除任意多条树边。对于第 $j$ 簇果实，当且仅当在第 $D_j$ 天，顶点 $V_j$ 已经不再与根位于同一连通块中，她才能获得 $W_j$ 的收益。

请计算萨什卡最多能够收获多少颗恰好成熟的樱桃李。

实现要求

你需要提交 cherryplum.cpp，包含 cherryplum.h，并实现：

long long solve(
    int N,
    int M,
    int K,
    const std::vector<int>& P,
    const std::vector<int>& V,
    const std::vector<int>& D,
    const std::vector<long long>& W
);

参数含义：

• $N$：树的顶点数；
• $M$：果实簇数量；
• $K$：最晚成熟日期；
• P 长度为 $N-1$，其中 P[i] 是顶点 $i+2$ 的父亲；
• V[j]、D[j]、W[j] 描述第 $j$ 簇果实所在顶点、成熟日期和收益。

保证 V 中的顶点两两不同。

函数只会被调用一次，应返回最大总收益。

数据范围

• $2\le N\le 100\,000$；
• $1\le M\le N-1$；
• $1\le K\le 100\,000$；
• $2\le V_j\le N$；
• $1\le D_j\le K$；
• $1\le W_j\le 10^9$。

子任务

本地评测器格式

输入

N M K
P2
P3
...
PN
V1 D1 W1
V2 D2 W2
...
VM DM WM

输出

输出 solve 的返回值。

样例

输入：
6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3

输出：
9

一种最优方案为：

• 第 $4$ 天，砍断顶点 $4$ 与 $5$ 之间的边，收获顶点 $5$ 的 $1$ 颗果实；同时砍断顶点 $1$ 与 $2$ 之间的边，收获顶点 $3$ 的 $5$ 颗果实；
• 第 $7$ 天不操作，放弃顶点 $4$ 的果实；
• 第 $9$ 天，砍断顶点 $1$ 与 $4$ 之间的边，收获顶点 $6$ 的 $3$ 颗果实。

总收益为 $1+5+3=9$。

@下发文件