3933: 茉莉花茶(jasmine)

jasmine.in/jasmine.out

Jasmine喜欢喝茉莉花茶.

Jasmine家里有一棵以1为根节点的树,树上的每个节点上有一种茉莉花茶.这些茉莉花茶的品种互不相同.如果一个点u是某个点v(u!=v)的祖先(也就是说,u位于1到v的路径上),那么我们就说v是u的”下属品种”.规定一个节点v也是节点v本身的”下属品种”

Jasmine很想给自己续命.每天,Jasmine都会喝两杯茉莉花茶.这两杯茉莉花茶的种类可以一样,也可以不一样.但是这两杯茶是有顺序的.也就是说,如果这两杯茶的种类不一样,那么这两杯茶喝下去的先后顺序不同时,会得到两种不同的喝法.

Jasmine认为,每有一种不同的喝法,他就能给自己续命1秒.

也就是说,如果这棵树本来有n个节点,Jasmine可以给自己续n²秒.

Jasmine认为有些茶一起喝的时候会出现偏差.

Jasmine规定了m个”冲突”,每个”冲突”包含两个节点u,v,如果一种喝法的两杯茶分别是u和v的”下属品种”,那么这种喝法被禁止.u可能 等于v,这个时候表示不能两杯茶都来自这一个节点的”下属品种”

Jasmine想知道他能给自己续多少秒.也就是说,有多少种没被禁止的喝法.

【样例解释1】

一条长度为3的链,没有冲突,所以有全部3*3=9种喝法.

【样例解释2】

只有一个”冲突”,且只影响了(3,3)这种喝法

【样例输入3】

3 2

1 2

2 3

3 3

【样例输出3】

6

【样例解释3】

有两个”冲突”,影响了(3,3)(2,3)(3,2)这3种喝法

【数据规模和约定】

对所有测试点,1<=n<=200000,0<=m<=100000,给出的节点父亲能够形成一棵以1为根的树.m个”冲突”中的节点编号都是1到n之间的整数 .

第1个测试点,满足m=0

第2,3个测试点,满足m=1

第4,5个测试点,所有”冲突”都满足u=v

第6,7个测试点,满足第i个节点的父亲是第i-1个节点.

第8,9,10个测试点,无特殊限制.

第一行两个整数n,m,之间用空格隔开,表示树的节点数n和冲突数m.

接下来一行n-1整数,之间用空格隔开,第i个数字表示第i+1个节点的父亲节点的编号.

接下来m行, 表示m对冲突.每行一对整数u,v, 表示一种喝法的两杯茶不能分别是u和v的”下属品种”.

一行一个整数表示Jasmine能给自己续多少秒

3 0
1 2

9