题目描述
已知 n 个顶点的有根树,以及 m 个二元组 (xi,yi),其中 xi,yi 是树的顶点。
对于树的顶点 a,b,定义 D(a,b) 为:在以 a 为根的子树中,但不在以 b 为根的子树中的顶点个数。
你需要求出以这些二元组为顶点的完全图的最小生成树,其中 (xi,yi) 和 (xj,yj) 之间的边权是 D(xi,xj)+D(xj,xi)+D(yi,yj)+D(yj,yi)。
输入格式
从标准输入读入数据。
第一行两个数表示 n,m。
之后一行 n−1 个数,其中第 i 个数表示编号为 i+1 的节点的父亲 fi+1,保证 fi+1<i+1。
之后 m 行,第 i 行两个数 xi,yi,表示一个给定的二元组。
输出格式
输出到标准输出。
输出一个整数,表示最小生成树的边权和。
样例数据
样例输入
5 4 1 2 3 3 3 5 2 2 5 2 2 5
样例输出
7
样例解释
最小生成树包含边 (1,4,1),(2,3,3),(2,4,3),三元组表示第一个二元组的编号,第二个二元组的编号,边权。边权和为 7。
子任务
对于 10% 的数据,满足 1≤n,m≤1000。
对于另外 10% 的数据,满足 1≤m≤2×104。
对于另外 10% 的数据,满足 1≤m≤5×104。
对于另外 20% 的数据,满足 m=n2,且每个二元组互不相同。
对于另外 10% 的数据,满足对任意 i=2⋯n,fi=i−1。
对于另外 10% 的数据,满足对任意 i=2⋯n,fi=1。
对于 100% 的数据,满足 1≤n≤106,1≤m≤105。对任意 i=1,2,…n−1,满足 1≤fi+1<i+1。对任意 i=1,2,…m,满足 1≤xi,yi≤n。