Distance to the Path

4000ms

524288K

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

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.

Sample Input:

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

Sample Output:

Note:

The tree from the first example:

$\text{[math]}$ 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\}$$$.

Informação

Provedor Codeforces

Código CF1749F