重链剖分 / 树链剖分

题目描述

给定一棵包含 $N$ 个结点的树，每个结点有一个非负整数权值。指定结点 $R$ 为根。你需要支持以下四种操作：

• 1 x y z：把结点 $x$ 到结点 $y$ 的最短路径上所有结点的权值都加上 $z$；
• 2 x y：求结点 $x$ 到结点 $y$ 的最短路径上所有结点的权值之和；
• 3 x z：把以结点 $x$ 为根的子树内所有结点的权值都加上 $z$；
• 4 x：求以结点 $x$ 为根的子树内所有结点的权值之和。

所有查询结果均对 $P$ 取模。

输入格式

第一行输入四个正整数 $N,M,R,P$，分别表示结点数、操作数、根结点编号和模数。

第二行输入 $N$ 个非负整数，表示各结点的初始权值。

接下来 $N-1$ 行，每行输入两个整数 $x,y$，表示结点 $x,y$ 之间有一条边。

接下来 $M$ 行，每行输入一个操作，格式见题目描述。

输出格式

对每个操作 2 或操作 4 输出一行，表示相应查询结果对 $P$ 取模后的值。

样例输入 1

5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3

样例输出 1

2
21

数据范围

• $1\le N,M\le 10^5$；
• $1\le R\le N$；
• $1\le P\le 2^{30}$；
• 所有输入整数均在 int 范围内。

样例说明

树的结构如下：

各次操作如下：

因此依次输出 $2$ 和 $21$。