CF276E.Little Girl and Problem on Trees

A little girl loves problems on trees very much. Here's one of them.

A tree is an undirected connected graph, not containing cycles. The degree of node x in the tree is the number of nodes y of the tree, such that each of them is connected with node x by some edge of the tree.

Let's consider a tree that consists of n nodes. We'll consider the tree's nodes indexed from 1 to n. The cosidered tree has the following property: each node except for node number 1 has the degree of at most 2.

Initially, each node of the tree contains number 0. Your task is to quickly process the requests of two types:

• Request of form: 0 v x d. In reply to the request you should add x to all numbers that are written in the nodes that are located at the distance of at most d from node v. The distance between two nodes is the number of edges on the shortest path between them.
• Request of form: 1 v. In reply to the request you should print the current number that is written in node v.

一个小女孩非常喜欢树上的问题。以下是其中一道题。

树是一种无向连通图，且不包含环。树中节点 $x$ 的度数是指树中与节点 $x$ 通过某条树边直接相连的节点 $y$ 的个数。

考虑一棵由 $n$ 个节点构成的树。我们将该树的节点编号为 $1$ 到 $n$。所考虑的这棵树具有如下性质：除节点 $1$ 外，其余每个节点的度数至多为 $2$。

初始时，树中每个节点上写的数均为 $0$。你需要高效地处理以下两类请求：

• 形如 0 v x d 的请求：作为对该请求的响应，你需要将所有与节点 $v$ 的距离不超过 $d$ 的节点上所写的数均加上 $x$。两个节点之间的距离定义为它们之间最短路径上的边数。
• 形如 1 v 的请求：作为对该请求的响应，你需要输出当前节点 $v$ 上所写的数。

The first line contains integers n (2 ≤ n ≤ 105) and q (1 ≤ q ≤ 105) — the number of tree nodes and the number of requests, correspondingly.

Each of the next n  -  1 lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i), that show that there is an edge between nodes u__i and v__i. Each edge's description occurs in the input exactly once. It is guaranteed that the given graph is a tree that has the property that is described in the statement.

Next q lines describe the requests.

• The request to add has the following format: 0 v x d (1 ≤ v ≤ n, 1 ≤ x ≤ 104, 1 ≤ d < n).
• The request to print the node value has the following format: 1 v (1 ≤ v ≤ n).

The numbers in the lines are separated by single spaces.

第一行包含两个整数 $n$（$2 \leq n \leq 10^5$）和 $q$（$1 \leq q \leq 10^5$），分别表示树的节点数和请求次数。

接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$），表示节点 $u_i$ 与 $v_i$ 之间存在一条边。每条边在输入中恰好出现一次。保证所给图是一棵树，且满足题目陈述中描述的性质。

接下来的 $q$ 行描述各个请求：

• 添加请求的格式为：0 v x d（其中 $1 \leq v \leq n$，$1 \leq x \leq 10^4$，$1 \leq d < n$）；
• 查询节点值请求的格式为：1 v（其中 $1 \leq v \leq n$）。

每行中的数字以单个空格分隔。

For each request to print the node value print an integer — the reply to the request.

对于每个打印节点值的请求，输出一个整数——该请求的答复。