树链剖分 [C++]P3384 轻重链剖分

[C++]树链剖分预备知识

树的基础知识
- 关于这个本文有介绍
邻接表存图
线段树基础
- 会区间加法和区间结合就可以了P3372
- 建议阅读这篇Blog
最近公共祖先LCA
- 虽然用不到这个思想但是有类似的
- 有助于快速理解代码
- 建议阅读这篇Blog

题意解读题目描述如题，已知一棵包含 \(N\) 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：
【树链剖分 [C++]P3384 轻重链剖分】操作 1：格式： \(1\) \(x\) \(y\) \(z\) 表示将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(z\) 。
操作 2：格式： \(2\) \(x\) \(y\) 表示求树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值之和。
操作 3：格式： \(3\) \(x\) \(z\) 表示将以 \(x\) 为根节点的子树内所有节点值都加上 \(z\) 。
操作 4：格式： \(4\) \(x\) 表示求以 \(x\) 为根节点的子树内所有节点值之和
输入格式第一行包含 44 个正整数 N,M,R,P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取模）。
接下来一行包含 N 个非负整数，分别依次表示各个节点上初始的数值。
接下来 N-1 行每行包含两个整数 x,y，表示点 x 和点 y 之间连有一条边（保证无环且连通）。
接下来 MM 行每行包含若干个正整数，每行表示一个操作，格式如下：
操作 1： x y z；
操作 2： x y；
操作 3： x z；
操作 4： x 。
输出格式输出包含若干行，分别依次表示每个操作 22 或操作 44 所得的结果（对 PP 取模）