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

给你一棵包含 $n$ 个顶点的树。初始时，每个顶点的值均为 $0$。

你需要执行 $m$ 个查询，查询分为两类：

1. 给定一个顶点编号 $v$，输出顶点 $v$ 的当前值。
2. 给定两个顶点编号 $u$ 和 $v$，以及两个数值 $k$ 和 $d$（其中 $d \le 20$）。你需要对所有满足“到 $u$ 到 $v$ 的路径的距离 $\le d$”的顶点，将其值增加 $k$。

两个顶点 $x$ 和 $y$ 之间的距离定义为从 $x$ 到 $y$ 的路径上的边数。例如，顶点 $x$ 到其自身的距离为 $0$。

顶点 $v$ 到某条从 $x$ 到 $y$ 的路径的距离，定义为 $v$ 到该路径上任意顶点的最小距离。

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.

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——树中顶点的数量。

接下来的 $n - 1$ 行描述树的边，每行一条边。每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$；$u \neq v$），表示树中的一条边。保证所给的边构成一棵树。

接下来一行包含一个整数 $m$（$1 \le m \le 2 \cdot 10^5$）——查询的数量。

接下来的 $m$ 行描述查询，每行一个查询。每个查询为以下两种类型之一：

• $1$ $v$（$1 \le v \le n$）——第一类查询；
• $2$ $u$ $v$ $k$ $d$（$1 \le u, v \le n$；$1 \le k \le 1000$；$0 \le d \le 20$）——第二类查询。

输入的附加约束：至少存在一个第一类查询。

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

第一个示例中的树：

部分查询说明：

• “$2$ $4$ $5$ $10$ $2$”：受影响的顶点为 $\{4, 2, 5, 1, 3\}$；
• “$2$ $1$ $1$ $10$ $20$” 和 “$2$ $6$ $6$ $10$ $20$”：所有顶点均受影响，因为任一顶点到顶点 $1$（即顶点 $6$）的距离均小于 $20$；
• “$2$ $3$ $2$ $10$ $0$”：受影响的顶点为 $\{3, 1, 2\}$；
• “$2$ $5$ $2$ $10$ $1$”：受影响的顶点为 $\{5, 2, 4, 1\}$。