#555. [NOIP2018模拟赛]小P的Civilization V

[NOIP2018模拟赛]小P的Civilization V

题目描述

小P最近在玩Civilization V,游戏的地图是一棵树,树的每个节点都可以当作战场,刚开始每个节点的战斗加成为00

现在小P拥有两种人员:

一种是工人,每个工人会有一个起点uu和终点vv,工人可以使u>vu->v路径上每个节点的战斗加成+1+1

一种是骑兵,每个骑兵也有一个起点uu和终点vv,骑兵可以选择u>vu->v路径上任意节点战斗

现有mm个工人和qq个骑兵,问每个骑兵作战最多可以拥有多少战斗加成

输入格式

第一行三个整数n,m,qn,m,q

接下来一行n1n-1个数,第ii个数fif_i表示第i+1i+1个节点的父亲

接下来mm行,每行两个整数u,vu,v,表示一个工人

接下来qq行,每行两个整数u,vu,v,表示一个骑兵

输出格式

qq行,对于每个骑兵,输出他作战最多可以拥有多少战斗加成

样例

样例输入1

5 5 5
1 1 1 4 
4 5
4 1
4 3
5 3
4 5
1 3
3 5
1 1
5 2
4 2

样例输出1

3
5
3
5
5

样例输入2

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

样例输出2

1
1
2
2
4

数据范围与提示

对于15%15\%的数据,保证n,m,q1000n,m,q\le 1000

对于另外15%15\%的数据,保证fi=if_i=i

对于另外10%10\%的数据,保证所有u=vu=v

对于另外10%10\%的数据,保证工人的u=vu=v

对于另外10%10\%的数据,保证骑兵的u=vu=v

对于100%100\%的数据,保证n,m,q500,000n,m,q\le 500,000fiif_i\le i