← 返回题目列表

Codeforces · 856/D

D. 玛莎和仙人掌

中文机器翻译题面 查看原题

玛莎喜欢仙人掌。当她还是个小女孩时,她决定种一棵树。现在玛莎想用她的树制作一棵漂亮的仙人掌。

回想一下,树是一个没有循环的无向连通图。 Cactus 是一种无向连通图,每个顶点最多属于一个环。

Masha 有一些额外的边可以添加到树上。对于每条边,她知道它将连接哪些顶点以及这条边的美感。如果生成的图是仙人掌,Masha 可以将其中一些边添加到图中。由此产生的仙人掌的美丽是所有添加边缘的美丽的总和。

帮助玛莎找出她能达到的仙人掌的最大美感。

输入

输入数据的第一行包含两个整数 n 和 m — 树中的顶点数以及可用的附加边数 (3 ≤ n ≤ 2·105;0 ≤ m ≤ 2·105)。

让我们描述一下玛莎的树。它的根位于顶点 1。第二行包含 n - 1 个整数:p2、p3、...、pn,这里 pi — 是顶点 i 的父节点 — 从顶点 i 到树根的路径上的第一个顶点 (1 ≤ pi < i)。

以下 m 行包含三个整数 ui、vi 和 ci — 由 Masha 可以添加到树中的附加边连接的顶点对以及边的美感 (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ ci ≤ 104)。

保证没有额外的边与树的边重合。

输出

输出一个整数——仙人掌玛莎所能达到的最大美感。

示例

输入 #1

7 3
1 1 2 2 3 3
4 5 1
6 7 1
2 3 1

输出 #1

2