5024 - 【模板】树套树套树

给你一棵n个节点的树,每个节点i有一个可重集A_i。你需要维护一个数据结构(可以参考标题),来维护以下几种操作:

  1. 1 x y z表示给x,y路径上所有的点的可重集都加一个数z
  2. 2 x y z表示求出x,y路径上所有的点的可重集的并集的第z大的数。
  3. 3 x y z表示求出x,y路径上所有的点的可重集的并集中有几个数比z小。

输入

第一行两个数n,m,表示节点数和操作数。

接下来n-1行,每行两个树表示一条树边。

接下来n行中第i行先有一个数x_i表示初始i号节点的可重集的大小,之后有x_i个数表示i号节点的可重集的各个元素(保证从小到大给出)

接下来m行,每行四个数op,x,y,z,表示一次操作

输出

对于所有的询问操作,分行输出答案。

样例

输入

10 10
1 2
2 3
3 4
2 5
5 6
6 7
7 8
2 9
1 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
3 4 10 3
1 4 9 2
3 4 10 3
1 6 10 9
2 6 10 9
1 8 10 998244353
1 8 4 123456789
1 4 10 987654321
2 8 10 20
3 1 10 56

输出

2
5
9
987654321
4

输入

10 10
2 1
3 1
4 1
5 1
6 1
7 1
8 7
9 2
10 2
3 1156 3479 6691
2 945 8407
1 6605
4 2077 2272 6251 9786
4 488 2007 2497 7865
2 1101 7389
2 3717 5896
1 3876
3 2801 9441 9926
3 6001 9081 9976
3 8 9 4704
2 8 5 1
2 7 5 3
2 4 2 5
1 7 2 7302
3 10 4 8825
1 5 9 1441
2 2 10 4
1 1 3 1549
3 1 9 4705

输出

6
488
2007
3479
11
7302
8

提示

对于33\%的数据,1\leq n,m\leq10

对于100\%的数据,n\leq10^4,m\leq5\times10^4,\sum\limits_{i=1}^nx_i\leq10^5

保证每个可重集的元素在[1,10^9]范围之内。

时间限制 5 秒
内存限制 2048 MB
讨论 统计
上一题 下一题