QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 2048 MB Total points: 100
[-6]

# 4408. 燃烧的呐球

统计

题目描述

已知 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

之后一行 n1 个数,其中第 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% 的数据,满足 1n,m1000

对于另外 10% 的数据,满足 1m2×104

对于另外 10% 的数据,满足 1m5×104

对于另外 20% 的数据,满足 m=n2,且每个二元组互不相同。

对于另外 10% 的数据,满足对任意 i=2nfi=i1

对于另外 10% 的数据,满足对任意 i=2nfi=1

对于 100% 的数据,满足 1n106,1m105。对任意 i=1,2,n1,满足 1fi+1<i+1。对任意 i=1,2,m,满足 1xi,yin