Description

Knight Company is a huge intelligence organization with a vast intelligence network. There are $n$ agents in the network. Each agent may have several (possibly none) subordinates. Except for one boss, each of the remaining $n-1$ agents has exactly one supervisor. The company has strict discipline: each agent may contact only their own supervisor and subordinates. Meanwhile, any two agents can pass intelligence through the network.

Each day, the company assigns exactly one of the following two tasks:

1. Collect intelligence: designate agent $T$ to start collecting intelligence.
2. Transmit intelligence: transmit a piece of intelligence from agent $X$ to agent $Y$.

Initially, all agents are in a dormant stage and are relatively safe; we consider their danger values to be $0$. Once an agent starts collecting intelligence, their danger value keeps increasing by $1$ per day (on the starting day, the danger value is still $0$; on the 2nd day it is $1$; on the 3rd day it is $2$; and so on). Transmission tasks do not increase any agent’s danger value.

To ensure safety during transmission, each piece of intelligence has a risk control value $C$. Among all agents who participate in transmitting this piece (i.e., those on the unique path between $X$ and $Y$, inclusive), any agent whose danger value is greater than $C$ is considered a threat to this piece.

For every transmission task, determine how many agents participate in the transmission and how many of them constitute a threat to this piece.

Input Format

• The first line contains a positive integer $n$, the number of agents.
• The second line contains $n$ non-negative integers. The $i$-th integer $P_i$ denotes the supervisor of agent $i$. In particular, if $P_i = 0$, agent $i$ is the boss.
• The third line contains a positive integer $q$, the number of tasks (one per day).
• The next $q$ lines each describe a task. Each line starts with a positive integer $k$:
  • If $k = 1$, it is a transmission task, followed by three positive integers $X_i$, $Y_i$, $C_i$, denoting the start, the end, and the risk control value, respectively.
  • If $k = 2$, it is a collection task, followed by one positive integer $T_i$, the agent who starts collecting intelligence.

Output Format

For each transmission task, output one line containing two integers: the number of participating agents and the number of agents who constitute a threat to this piece of intelligence.

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

5 0
5 2
5 1

Hint

Sample explanation:

For the $3$ transmission tasks, each passes through $5$ agents, namely $4$, $2$, $1$, $3$, and $7$.

• In the 1st task, all agents (danger value $0$) do not constitute a threat.
• In the 2nd task, there are $2$ threatening agents: agent $1$ (danger value $3$) and agent $4$ (danger value $2$). Agent $7$ (danger value $1$) is not a threat.
• In the 3rd task, only $1$ agent is a threat.

Constraints:

$n \le 2 \times 10^5$, $q \le 2 \times 10^5$, $0 \le P_i, C_i \le n$, $1 \le T_i, X_i, Y_i \le n$.

Translated by ChatGPT 5