Distance to the Path
Description
You are given a tree consisting of $n$ vertices. Initially, each vertex has a value $0$.
You need to perform $m$ queries of two types:
- You are given a vertex index $v$. Print the value of the vertex $v$.
- You are given two vertex indices $u$ and $v$ and values $k$ and $d$ ($d \le 20$). You need to add $k$ to the value of each vertex such that the distance from that vertex to the path from $u$ to $v$ is less than or equal to $d$.
The distance between two vertices $x$ and $y$ is equal to the number of edges on the path from $x$ to $y$. For example, the distance from $x$ to $x$ itself is equal to $0$.
The distance from the vertex $v$ to some path from $x$ to $y$ is equal to the minimum among distances from $v$ to any vertex on the path from $x$ to $y$.
The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.
Next $n - 1$ lines contain the edges of the tree — one per line. Each line contains two integers $u$ and $v$ ($1 \le u, v \le n$; $u \neq v$) representing one edge of the tree. It's guaranteed that the given edges form a tree.
The next line contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of queries.
Next $m$ lines contain the queries — one per line. Each query has one of the following two types:
- $1$ $v$ ($1 \le v \le n$) — the query of the first type;
- $2$ $u$ $v$ $k$ $d$ ($1 \le u, v \le n$; $1 \le k \le 1000$; $0 \le d \le 20$) — the query of the second type.
Additional constraint on the input: there is at least one query of the first type.
For each query of the first type, print the value of the corresponding vertex.
Input
The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.
Next $n - 1$ lines contain the edges of the tree — one per line. Each line contains two integers $u$ and $v$ ($1 \le u, v \le n$; $u \neq v$) representing one edge of the tree. It's guaranteed that the given edges form a tree.
The next line contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of queries.
Next $m$ lines contain the queries — one per line. Each query has one of the following two types:
- $1$ $v$ ($1 \le v \le n$) — the query of the first type;
- $2$ $u$ $v$ $k$ $d$ ($1 \le u, v \le n$; $1 \le k \le 1000$; $0 \le d \le 20$) — the query of the second type.
Additional constraint on the input: there is at least one query of the first type.
Output
For each query of the first type, print the value of the corresponding vertex.
6
1 2
1 3
4 2
5 2
3 6
14
2 4 5 10 2
1 3
1 6
2 1 1 10 20
2 6 6 10 20
1 3
2 3 2 10 0
2 5 2 10 1
1 1
1 2
1 3
1 4
1 5
1 6
10
0
30
50
50
40
40
40
20
Note
The tree from the first example:
- "$2$ $4$ $5$ $10$ $2$": affected vertices are $\{4, 2, 5, 1, 3\}$;
- "$2$ $1$ $1$ $10$ $20$" and "$2$ $6$ $6$ $10$ $20$": all vertices are affected, since distance to $1$ ($6$) is less that $20$ for any vertex;
- "$2$ $3$ $2$ $10$ $0$": affected vertices are $\{3, 1, 2\}$;
- "$2$ $5$ $2$ $10$ $1$": affected vertices are $\{5, 2, 4, 1\}$.