UOJ Logo

NOI.AC

1S 512MB

#229. track

统计

【问题描述】

现有一个 N 个节点的有根树,根为1号节点,且每个节点有一个颜色。

现有若干询问,每个询问为一组颜色(Ci,Cj), 问有多少点对(ai,aj)满足ai的颜色是Ci, aj的颜色是Cjajai的祖先。题目的询问还有一个有趣的性质,两种颜色中一定存在一种颜色其节点个数不超过n.

【输入格式】

输入第一行包含一个正整数n, r,表示树的节点数和颜色数。

输入第二行至第 n 行中,每行包含1个正整数,表示第 i 号节点的父亲节点编号,由于1是根节点,所以只有 n-1 行。

输入第 n + 1 行包含 n 个正整数,表示节点的颜色。

接下来一行包含一个正整数 q , 表示询问数。

接下来的 q 行, 每行包含两个正整数,表示一组颜色的询问(Ci,Cj)

本题需要大家设计在线的做法,每组询问的颜色标号(都需要)需要减去上一次的答案,第一次的询问为正常询问,不需要特殊处理。

【输出格式】

输出共 t 行,每行一个数表示所求的节点对的个数。

【输入输出样例 1】

track.in

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

track.out

2
1

【数据规模与约定】

对于 30% 的数据,n1000

对于另外 20% 的数据,满足询问(Ci,Cj),中 Ci 的节点数不超过n.

对于另外 20% 的数据,满足询问(Ci,Cj),中 CJ的节点数不超过n.

对于100% 的数据,n,Ci,q10000