CF1749F.Distance to the Path

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:

1. You are given a vertex index $v$ . Print the value of the vertex $v$ .
2. 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.

The tree from the first example:

Some query explanations: - " $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\}$ .