P11840 [USACO25FEB] Vocabulary Quiz S

题目描述

给出一棵有 $N+1$ 个点有根树，根节点为 $0$，节点编号为$0$ ～ $N$。第 $i$ 个节点的父亲节点为 $p_i(0 \le p_i < i)$ ，每条边单位为 $1$ 。

假设整棵树有 $M$个叶子节点 ，每个叶子 $w_i$ 住着一个学生，学生编号也为 $w_i$。

$0$ 号点是学校，每天放学同学们从 $0$ 点出发，回到各自的叶子节点。

某天放学，同学们按编号 $w_1,w_2,\dots,w_M$的顺序走最短路回家（ $w_1$ 到家后，$w_2$ 才开始放学，依次类推），每个节点都有一头路霸牛驻守（包括根节点和叶子节点），路霸牛不认识学生们，但提前了解整棵树的具体结构，且清楚哪些编号的学生会路过自己驻守的点。

当学生路过的一个点时，

• 如果驻守的路霸牛能确定该学生的编号，则学生需要上交给改节点的路霸牛 $c$ 个硬币作为过路费（$c$等于该点到根节点的距离），每个学生只会交一次过路费，交过之后路过其他节点则无需再交。
• 如果驻守的路霸牛不能确认学生编号，也会原地站着一直看着学生走到叶子节点，并且记录该学生的编号。显然这有助于确定下来路过该节点的学生的编号，好收取过路费（如果路过该点总共有 $k$ 个学生，现在已经路过$k-1$个，根据这$k-1$个学生到达的叶子节点的编号确定这 $k-1$ 个学生的编号，那么当最后一个学生来的时候，就能确定该学生的编号）。

问每个学生各需准备多少硬币作为回家的过路费。

输入格式

第一行一个整数 $N \ (1\le N \le 10^7)$。

下来 N 个整数 $p_i$。

下来 $M$（题目没有给出$M$，需要自己求） 个整数 $w_1,w_2,\dots,w_M$。

输出格式

输出 $M$ 行，每行一个整数，表示编号 $w_i$ 的学生回家的过路费。

输入输出样例 #1

输入 #1

5
0 1 2 3 4
5

输出 #1

0

输入输出样例 #2

输入 #2

4
0 0 1 1
4
3
2

输出 #2

2
1
0

输入输出样例 #3

输入 #3

4
0 0 1 1
2
3
4

输出 #3

1
2
0

说明/提示

样例 1 解释：

只有一个叶子节点 $5$ ，编号为 $5$ 的学生一放学就在 $0$ 号节点被路霸牛确认出他的编号。