QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 2048 MB Total points: 100

# 4408. 燃烧的呐球

Statistics

题目描述

已知 $n$ 个顶点的有根树,以及 $m$ 个二元组 $(x_i,y_i)$,其中 $x_i,y_i$ 是树的顶点。

对于树的顶点 $a,b$,定义 $D(a,b)$ 为:在以 $a$ 为根的子树中,但不在以 $b$ 为根的子树中的顶点个数。

你需要求出以这些二元组为顶点的完全图的最小生成树,其中 $(x_i,y_i)$ 和 $(x_j,y_j)$ 之间的边权是 $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$。

输入格式

从标准输入读入数据。

第一行两个数表示 $n,m$。

之后一行 $n-1$ 个数,其中第 $i$ 个数表示编号为 $i+1$ 的节点的父亲 $f_{i+1}$,保证 $f_{i+1}< i+1$。

之后 $m$ 行,第 $i$ 行两个数 $x_i,y_i$,表示一个给定的二元组。

输出格式

输出到标准输出。

输出一个整数,表示最小生成树的边权和。

样例数据

样例输入

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\le n,m\le 1000$。

对于另外 $10\%$ 的数据,满足 $1\le m\le 2\times 10^4$。

对于另外 $10\%$ 的数据,满足 $1\le m\le 5\times 10^4$。

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

对于另外 $10\%$ 的数据,满足对任意 $i=2\cdots n$,$f_i=i-1$。

对于另外 $10\%$ 的数据,满足对任意 $i=2\cdots n$,$f_i=1$。

对于 $100\%$ 的数据,满足 $1\le n\le 10^6,1\le m\le 10^5$。对任意 $i=1,2,\dots n-1$,满足 $1\le f_{i+1} < i+1$。对任意 $i=1,2,\dots m$,满足 $1\le x_i,y_i\le n$。