Comet OJ

C1108 [SCOI2015]情报传递

内存限制：512 MB 时间限制：1500 ms

题目描述

奈特公司是一个巨大的情报公司，它有着庞大的情报网络。情报网络中共有 $n$ 名情报员。每名情报员可能有若干名（可能没有）下线，除 $1$ 名大头目外其余 $n - 1$ 名情报员有且仅有 $1$ 名上线。奈特公司纪律森严，每名情报员只能与自己的上、下线联系，同时，情报网络中仟意两名情报员一定能够通过情报网络传递情报。

奈特公司每天会派发以下两种任务中的一个任务：

  1. 搜集情报：指派 $T$ 号情报员搜集情报；

  2. 传递情报：将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员。

情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为 $0$；一旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加 $1$ 点危险值（开始搜集情报的当天危险值仍为 $0$，第 $2$ 天危险值为 $1$，第 $3$ 天危险值为 $2$，以此类推）。传递情报并不会使情报员的危险值增加。

为了保证传递情报的过程相对安全，每条情报都有一个风险控制值 $C$。奈特公司认为，参与传递这条情报的所有情报员中，危险值大于 $C$ 的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。

输入格式

第一行包含一个正整数 $n$，表示情报员个数。

笫二行包含 $n$ 个非负整数，其中第 $i$ 个整数 $P_i$ 表示 $i$ 号情报员上线的编号。特别地，若 $P_i = 0$，表示 $i$ 号情报员是大头目。

第三行包含一个正整数 $q$，表示奈特公司将派发 $q$ 个任务（每天一个）。

随后 $q$ 行，依次描述 $q$ 个任务。

每行首先有一个正整数 $k$。

  • 若 $k = 1$，表示任务是传递情报，随后有三个正整数 $X_i$、$Y_i$、$C_i$，依次表示传递情报的起点、终点和风险控制值；

  • 若 $k = 2$，表示任务是搜集情报，随后有 $1$ 个正整数 $T_i$，表示搜集情报的情报员编号。

输出

对于每个传递情报任务输出一行，应包含两个整数，分别是参与传递情报的情报员个数和对该条情报构成威胁的情报员个数。

输出的行数应等于传递情报任务的个数，每行仅包含两个整数，用一个空格隔开。输出不应包含多余的空行和空格。

样例

样例输入 1

7
0 1 1 2 2 3 3 
6
1 4 7 0
2 1
2 4
2 7
1 4 7 1
1 4 7 3

样例输出 1

5 0
5 2
5 1

提示

$n \leq 2 \times 10 ^ 5, Q \leq 2 \times 10 ^ 5, 0 < P_i, C_i \leq N, 1 \leq T_i, X_i, Y_i \leq n$