#4309. Maishroom & Mushroom

内存限制:512 MiB 时间限制:20 Sec

题目描述

Maishroom有一个蘑菇,我们不妨称它为蘑菇1。蘑菇上有n个room,这些room按1..n编号,并组成了一棵树,其中room 1是根。由于Maishroom长期没有修剪,蘑菇1的每个room 里都长满了杂草。
众所周知Maishroom非常喜欢蘑菇,于是它对这个蘑菇进行了一系列操作,包括复制、合并、修剪和询问。这些操作的具体说明如下:
操作 格式 说明
复制 1 u Maishroom复制了蘑菇u,新的蘑菇编号为cnt+1。
合并 2 u v Maishroom将蘑菇v合并到了蘑菇u上。当然,如果某个旧蘑菇的某个room有杂草,新的蘑菇u的对应room中也会有杂草。合并完后蘑菇v不会消失。
修剪1 3 u v Maishroom除去了蘑菇u上以room x为根的子树上的杂草。
修剪2 4 u v Maishroom几乎除去了蘑菇u上所有的杂草,除了以room x为根的子树上的那些。
修剪3 5 u x y Maishroom除去了蘑菇u上room x到room y 路径上的杂草。
修剪4 6 u x y Maishroom几乎除去了蘑菇u上所有的杂草,除了room x到room y路径上的那些。
修剪5 7 u l r Maishroom除去了蘑菇u上编号在L到r之间(包括L,R)的room中的杂草。
修剪6 8 u l r Maishroom几乎除去了蘑菇u上所有的杂草,除了编号在L到r之间(包括L,r)的room 中的那些。
询问 9 u w Maishroom想知道清除蘑菇u上所有杂草所需的时间。Maishroom有一种工具来清除蘑菇上的杂草,每使用一次Maishroom可以选定一个蘑菇上编号的极差不超过w的一些room并清除它们中的杂草,使用一次消耗一个单位的时间。
注:表中的cnt表示该操作进行之前Maishroom拥有的蘑菇数。
现在有一份Maishroom的操作记录,你的任务是回答Maishroom的每个询问。

输入格式

第一行一个整数n,表示蘑菇上room的个数。
接下来n-1行,每行两个整数x,y,表示room x,y之间有一条边。
接下来一行一个整数q,表示Maishroom的操作次数。
接下来q行,每行表示Maishroom的一个操作。

输出格式

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

样例

样例输入


			
5
1 3
3 5
1 2
2 4
9
1 1
1 2
5 3 4 5
9 3 0
2 3 2
6 3 4 5
9 3 1
4 2 2
9 2 1

样例输出


			
0
3
2

数据范围与提示

N<=50000,Q<=100000,W[0,200]中随机