CF276E Little Girl and Problem on Trees

有一个小女孩非常喜欢有关树的数据结构题目。以下是一道有关树的问题。 树是一种无环的连通无向图。在树中，节点 $x$ 的度数定义为与节点 $x$ 直接通过树中的一条边相连的不同节点 $y$ 的数量。 现在给定一棵包含 $n$ 个节点的树。树的节点编号为 $1$ 到 $n$。已知该树满足如下性质：除编号为 $1$ 的节点以外，每个节点的度数都不超过 $2$。 一开始，每个节点上都写有数字 $0$。你需要快速处理两种操作请求： - 类型 $0$ 请求：$0\ v\ x\ d$，表示将与节点 $v$ 的距离不超过 $d$ 的所有节点上的数值加上 $x$。两节点之间的距离定义为它们之间最短路径上的边数。 - 类型 $1$ 请求：$1\ v$，询问当前节点 $v$ 上的数值。

第一行包含两个整数 $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)$ 数字之间均由单个空格隔开。

对于每个查询请求，输出一行一个整数，表示该节点当前的数值。

由 ChatGPT 5 翻译