A15546 | 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.