#Algo0512. 【模板】轻重链剖分/树链剖分

    ID: 142 远端评测题 1000ms 128MiB 尝试: 10 已通过: 5 难度: 10 上传者: 标签>图论树链剖分数据结构线段树模板树状数组luogu

【模板】轻重链剖分/树链剖分

题目描述

如题,已知一棵包含 NN 个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作:

  • 1 x y z,表示将树从 xxyy 结点最短路径上所有节点的值都加上 zz

  • 2 x y,表示求树从 xxyy 结点最短路径上所有节点的值之和。

  • 3 x z,表示将以 xx 为根节点的子树内所有节点值都加上 zz

  • 4 x 表示求以 xx 为根节点的子树内所有节点值之和

输入格式

第一行包含 44 个正整数 N,M,R,PN,M,R,P,分别表示树的结点个数、操作个数、根节点序号和取模数(即所有的输出结果均对此取模)。

接下来一行包含 NN 个非负整数,分别依次表示各个节点上初始的数值。

接下来 N1N-1 行每行包含两个整数 x,yx,y,表示点 xx 和点 yy 之间连有一条边(保证无环且连通)。

接下来 MM 行每行包含若干个正整数,每行表示一个操作。

输出格式

输出包含若干行,分别依次表示每个操作 22 或操作 44 所得的结果(PP 取模)。

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
2
21

提示

【数据规模】

对于 30%30\% 的数据: 1N101 \leq N \leq 101M101 \leq M \leq 10

对于 70%70\% 的数据: 1N1031 \leq N \leq {10}^31M1031 \leq M \leq {10}^3

对于 100%100\% 的数据: 1N1051\le N \leq {10}^51M1051\le M \leq {10}^51RN1\le R\le N1P2301\le P \le 2^{30}。所有输入的数均在 int 范围内。

【样例说明】

树的结构如下:

各个操作如下:

故输出应依次为 222121