树链剖分

树链剖分

Background

树剖

Description

给定一个n个点的树,支持链加,链最大,子树加,子树最大。(1号点为root)

Input

第一行两个数n,m表示结点数和操作次数。
下n-1行每行2个数表示边。
下面m行,每行一个opt,
opt=1是链加操作,接下来三个数u,v,x,表示u-v链上加上x;
opt=2是查询链最大,接下来两个数u,v表示查询u-v链最大。
opt=3是子树加,接下来两个数u,x,表示u的子树加x;
opt=4是查询子树最大,接下来一个数u,表示查询u的子树最大。

Output

对于每个询问,输出一行表示答案。

Sample 1

Input

7 5
1 2
2 3
2 4
1 5
5 6
6 7
1 1 3 5
2 2 5
3 2 5
4 1
4 2

Output

5
10
10

Limitation

0.6s,256MB

Hint

对于20%的数据,n<=5000,m<=5000;
对于60%的数据,n<=50000,m<=50000;
对于100%的数据,n<=300000,m<=300000。
操作中的|x|<=1000。

信息

难度
8
分类
树结构 | 树链剖分 点击显示
标签
(无)
递交数
22
已通过
3
通过率
14%
上传者