CF856D Masha and Cactus

Masha 喜欢仙人掌。当她还是个小女孩的时候，她决定种一棵树。现在，Masha 想要将她的树变成一个漂亮的仙人掌。 回忆一下，树是一个连通无环无向图。仙人掌是一个连通无向图，使得每个顶点至多属于一个环。 Masha 有一些可以加到树上的附加边。对于每条边，她知道这条边连接的是哪两个顶点以及这条边的美丽值。Masha 可以选择将这些边中的一些加入图中，前提是加入后得到的图依然是仙人掌。结果仙人掌的美丽值是所有被加入边的美丽值之和。 帮助 Masha 求得她能获得的最大美丽值。

输入的第一行为两个整数 $n$ 和 $m$，分别表示树的顶点个数和可用附加边的数量（$3 \leq n \leq 2 \cdot 10^{5}$，$0 \leq m \leq 2 \cdot 10^{5}$）。 接下来描述 Masha 种下的树。树是以顶点 1 为根的。第二行为 $n-1$ 个整数：$p_2,p_3,\ldots,p_n$，其中 $p_i$ 表示顶点 $i$ 的父节点——从顶点 $i$ 到根节点的路径上的第一个顶点（$1 \leq p_i < i$）。 接下来的 $m$ 行，每行包含三个整数 $u_i$、$v_i$、$c_i$，表示 Masha 可以加入的附加边连接的两个顶点及其美丽值（$1 \leq u_i, v_i \leq n$，$u_i \ne v_i$，$1 \leq c_i \leq 10^4$）。 保证没有附加边与树上的边重复。

输出一个整数，表示 Masha 能获得的最大仙人掌美丽值。

由 ChatGPT 5 翻译