Distance to the Path
Contest: Educational Codeforces Round 138 (Rated for Div. 2)
Difficulty rating: 2800
Tags: data structures, dfs and similar, trees

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

Input format:
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 format:
For each query of the first type, print the value of the corresponding vertex.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

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

Example 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

Example output:
10
0
30
50
50
40
40
40
20

Editorial:
For the purpose of solving the task, let's choose some root in the tree and introduce another operation to the tree: add $$$k$$$ to all vertices that are in the subtree of the given vertex $$$v$$$ and on the distance $$$d$$$ from $$$v$$$. For example, if $$$d = 0$$$, it's $$$v$$$ itself or if $$$d = 1$$$ then it's all children of $$$v$$$.
Let's $$$p[v]$$$ be the parent of vertex $$$v$$$, $$$p^2[v] = p[p[v]]$$$, $$$p^3[v] = p[p[p[v]]]$$$ and so on ($$$p^0[v] = v$$$). So, how to perform this operation? Instead of adding $$$k$$$ to all vertices in the subtree, we can add $$$k$$$ only to the vertex $$$v$$$. And when we need to get the answer for some vertex $$$u$$$, we will get it from $$$ans[p^d[u]]$$$.
Of course, since there are different $$$d$$$-s, we'll create different arrays $$$ans_d$$$ for each possible $$$d$$$. So, the answer for the vertex will be equal to $$$\sum_{i=0}^{d}{ans_i[p^i[d]]}$$$.
Now, let's discuss how to use the introduced operation to perform the given one. We can make the given operation "$$$u$$$ $$$v$$$ $$$k$$$ $$$d$$$" using ours in the following way:
1. Let's find $$$l = lca(u, v)$$$ using any standard algorithm (binary lifting, for example).
2. Let's split all affected vertices in three groups: subtrees of path $$$[v, l)$$$ ($$$v$$$ inclusive, $$$l$$$ exclusive), subtrees of path $$$[u, l)$$$ and subtrees of path $$$l, p[l], p^2[l], \dots, p^d[l]$$$. Note that in such way all affected vertices belong to at least one group.
3. Let's look at group of path $$$[v, l)$$$. The lowest vertices are on distance $$$d$$$ from $$$v$$$, the next "level" are on distance $$$d$$$ from $$$p[v]$$$, the next "level" are on distance $$$d$$$ from $$$p^2[v]$$$ and so on. The last "level" we'll consider in this group is the vertices in the subtree of the child of $$$l$$$ on distance $$$d$$$ from it. In such a way, all we need to do is add $$$k$$$ to all $$$ans_d$$$ on the path from $$$[v, l)$$$.
4. The group of the path $$$[u, l)$$$ is handled in the same way.
5. What's left? It's vertices   in subtree of $$$l$$$ on distances $$$d, (d-1), \dots, 0$$$;  in subtree of $$$p[l]$$$ on distances $$$(d-1), (d-2), \dots, 0$$$;  in subtree of $$$p^i[l]$$$ on distances $$$(d-i), (d-i-1), \dots, 0$$$;  in subtree of $$$p^d[l]$$$ on distance $$$0$$$.  Note that vertices in subtree of $$$l$$$ on distance $$$d-2$$$ are included in vertices in subtree of $$$p[l]$$$ on distance $$$d-1$$$. Analogically, vertices on distance $$$d-3$$$ from $$$l$$$ are included in vertices on distance $$$d-2$$$ from $$$p[l]$$$.Moreover, vertices on distance $$$d-4$$$ from $$$l$$$ are included in "$$$d-3$$$ from $$$p[l]$$$" that are included in "$$$d-2$$$ from $$$p^2[l]$$$" and so on. In other words, all we need to proccess are vertices:   in subtree of $$$l$$$ on distances $$$d$$$ and $$$(d-1)$$$,  in subtree of $$$p[l]$$$ on distances $$$(d-1)$$$ and $$$(d-2)$$$,  in subtree of $$$p^i[l]$$$ on distances $$$(d-i)$$$ and $$$(d-i-1)$$$.  In total, it's at most $$$2d$$$ operations: "add $$$k$$$ to some vertex $$$x$$$".
6. in subtree of $$$l$$$ on distances $$$d, (d-1), \dots, 0$$$;
7. in subtree of $$$p[l]$$$ on distances $$$(d-1), (d-2), \dots, 0$$$;
8. in subtree of $$$p^i[l]$$$ on distances $$$(d-i), (d-i-1), \dots, 0$$$;
9. in subtree of $$$p^d[l]$$$ on distance $$$0$$$.
10. in subtree of $$$l$$$ on distances $$$d$$$ and $$$(d-1)$$$,
11. in subtree of $$$p[l]$$$ on distances $$$(d-1)$$$ and $$$(d-2)$$$,
12. in subtree of $$$p^i[l]$$$ on distances $$$(d-i)$$$ and $$$(d-i-1)$$$.
As a result, all we need to do is
1. add $$$k$$$ on path from $$$v$$$ to some ancestor $$$l$$$ of $$$v$$$;
2. add $$$k$$$ in some vertex $$$v$$$ (can be done as operation $$$1$$$ on path $$$[v, p[v])$$$);
3. ask value in some vertex $$$v$$$.
In total, complexity is $$$O(n \log{n} + m d \log{n})$$$ time and $$$O(n (\log{n} + d))$$$ space.
P.S.: the second operation can be further optimized to $$$O(d + \log{n})$$$, but it's not really necessary.