Distance to the Path

题意翻译

给你一棵树，点有点权，初始为$0$，两种操作： - 询问点权。 - 将树上所有到从 $u$ 到 $v$ 的路径的距离不超过 $d$ 的点的点权加上 $k$。 $n,q\le 2\times 10^5,d\le 20.$

题目描述

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.

输入输出样例

输入样例 #1

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

输出样例 #1

10
0
30
50
50
40
40
40
20

说明

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

**题意翻译**

给你一棵树，点有点权，初始为0，两种操作：

- 询问点权。
- 将树上所有到从 $u$ 到 $v$ 的路径的距离不超过 $d$ 的点的点权加上 $k$。

$n,q\le 2\times 10^5,d\le 20.$

**题目描述**

给定一棵由 $n$ 个顶点组成的树。最初，每个顶点都有一个值 $0$。

你需要执行 $m$ 个查询，查询有两种类型：

1. 给你一个顶点索引 $v$。打印顶点 $v$ 的值。
2. 给你两个顶点索引 $u$ 和 $v$ 以及值 $k$ 和 $d$（$d \le 20$）。你需要将 $k$ 加到每个顶点的值上，使得该顶点到从 $u$ 到 $v$ 的路径的距离小于或等于 $d$。

两个顶点 $x$ 和 $y$ 之间的距离等于从 $x$ 到 $y$ 的路径上的边数。例如，从 $x$ 到 $x$本身的距离等于 $0$。

顶点 $v$ 到某条从 $x$ 到 $y$ 的路径的距离等于从 $v$ 到路径上任意顶点的距离的最小值。

**输入输出格式**

**输入格式**

第一行包含一个整数 $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$）——第二种类型的查询。

输入的附加约束：至少有一个第一种类型的查询。

**输出格式**

对于每个第一种类型的查询，打印相应顶点的值。

**输入输出样例**

**输入样例 #1**

```
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
```

**输出样例 #1**

```
10
0
30
50
50
40
40
40
20
```

**说明**

第一个例子中的树：


一些查询解释：

- "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}。**题意翻译** 给你一棵树，点有点权，初始为0，两种操作： - 询问点权。 - 将树上所有到从 $u$ 到 $v$ 的路径的距离不超过 $d$ 的点的点权加上 $k$。 $n,q\le 2\times 10^5,d\le 20.$ **题目描述** 给定一棵由 $n$ 个顶点组成的树。最初，每个顶点都有一个值 $0$。 你需要执行 $m$ 个查询，查询有两种类型： 1. 给你一个顶点索引 $v$。打印顶点 $v$ 的值。 2. 给你两个顶点索引 $u$ 和 $v$ 以及值 $k$ 和 $d$（$d \le 20$）。你需要将 $k$ 加到每个顶点的值上，使得该顶点到从 $u$ 到 $v$ 的路径的距离小于或等于 $d$。 两个顶点 $x$ 和 $y$ 之间的距离等于从 $x$ 到 $y$ 的路径上的边数。例如，从 $x$ 到 $x$本身的距离等于 $0$。 顶点 $v$ 到某条从 $x$ 到 $y$ 的路径的距离等于从 $v$ 到路径上任意顶点的距离的最小值。 **输入输出格式** **输入格式** 第一行包含一个整数 $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$）——第二种类型的查询。 输入的附加约束：至少有一个第一种类型的查询。 **输出格式** 对于每个第一种类型的查询，打印相应顶点的值。 **输入输出样例** **输入样例 #1** ``` 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 ``` **输出样例 #1** ``` 10 0 30 50 50 40 40 40 20 ``` **说明** 第一个例子中的树：  一些查询解释： - "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}。