P3384 【模板】重链剖分/树链剖分
题目描述
如题，已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
- `1 x y z`，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。
- `2 x y`，表示求树从 $x$ 到 $y$ 结点最短路径上所有节点的值之和。
- `3 x z`，表示将以 $x$ 为根节点的子树内所有节点值都加上 $z$。
- `4 x` 表示求以 $x$ 为根节点的子树内所有节点值之和
输入格式
无
输出格式
无
说明/提示
**【数据规模】**
对于 $30\%$ 的数据： $1 \leq N \leq 10$，$1 \leq M \leq 10$；
对于 $70\%$ 的数据： $1 \leq N \leq {10}^3$，$1 \leq M \leq {10}^3$；
对于 $100\%$ 的数据： $1\le N \leq {10}^5$，$1\le M \leq {10}^5$，$1\le R\le N$，$1\le P \le 2^{30}$。所有输入的数均在 `int` 范围内。
**【样例说明】**
树的结构如下：
各个操作如下：
故输出应依次为 $2$ 和 $21$。