H. Homeland rescue
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Country A is renowned for its picturesque landscapes. It consists of $$$n$$$ cities, each with its unique charm, forming a vast and splendid nation. However, due to the financial crisis, the national budget is tight. As a result, there are only $$$n-1$$$ bidirectional roads connecting the $$$n$$$ cities. These $$$n-1$$$ roads ensure that it is possible to travel from any city to any other.

The administrative structure of Country A is well-organized: City $$$1$$$ is the capital. Every other city has a superior city. Specifically, for city $$$i$$$ ($$$i \ge 2$$$), there is a road connecting it to its superior city $$$fa_i$$$ ($$$1 \le fa_i \lt i$$$), and the length of this road is $$$w_i$$$.

A city $$$y$$$ is called an indirect subordinate of city $$$x$$$ if and only if the superior city $$$fa_y$$$ of $$$y$$$ is $$$x$$$, or $$$fa_y$$$ is an indirect subordinate of $$$x$$$.

Let $$$\mathrm{dist}(x, y)$$$ denote the length of the shortest path between city $$$x$$$ and city $$$y$$$.

Due to the rugged terrain and frequent natural disasters in Country A, the central command needs precise coordination and must balance the total workload of the fire rescue forces across cities.

The workload of the fire rescue force in city $$$i$$$ is defined as $$$a_i$$$. When the fire rescue force of city $$$i$$$ is dispatched to city $$$x$$$ for a mission, the workload increases by $$$\mathrm{dist}(i, x)$$$, i.e., $$$a_i \leftarrow a_i + \mathrm{dist}(i, x)$$$. Initially, the workload of every city is $$$0$$$.

The central command issues $$$q$$$ instructions in total:

  • $$$1\ x\ y$$$: Mission execution — A disaster occurs in city $$$y$$$. The fire rescue forces of city $$$x$$$ and all its indirect subordinates are dispatched to city $$$y$$$ to provide support, each performing one mission to city $$$y$$$.
  • $$$2\ x$$$: Workload query — Query the sum of workloads of the fire rescue forces of city $$$x$$$ and all its indirect subordinates.
Input

The first line contains two integers $$$n, q$$$ ($$$1 \le n, q \le 5 \times 10^5$$$), the number of cities and the number of instructions, respectively.

The next $$$n-1$$$ lines each contain two integers $$$fa_{i+1}, w_{i+1}$$$ ($$$1 \le fa_{i+1} \lt i+1$$$, $$$1 \le w_{i+1} \le 100$$$), where the two integers on the $$$i$$$-th line represent the superior city of city $$$i+1$$$ and the length of the road connecting them.

The next $$$q$$$ lines each contain one instruction in one of the following forms:

  • $$$1\ x\ y$$$ ($$$1 \le x, y \le n$$$): a type-1 instruction — mission execution;
  • $$$2\ x$$$ ($$$1 \le x \le n$$$): a type-2 instruction — workload query.
Output

For each type-2 instruction, output a single integer on a line — the total workload.

Example
Input
5 4
1 3
1 2
2 1
2 2
1 5 1
2 1
1 2 3
2 2
Output
5
23