#5081. 树

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

题目描述

给出一棵n个点的树,每个点有两层,每层有权值和颜色(黑白)。要
求支持以下操作。
1. Cover s t color,将 s 到 t 的路径上的点的两层的颜色全部置为 color(0
白 1 黑)
2. CVal index layer val 将 index 号点的 layer 层的权值修改为 val
3. CColor index layer color 将 index 号点的 layer 层的颜色修改为 color
4. QMax s t 询问 s 到 t 的路径上的白色最大权值和路径的权值(任意
白色层为起点,每次只能往相同点不同层或者相邻点同一层上移动,
每个点的每一层最多走一次,路径经过的层必须都是白色),若 s 到
t 上的路径没有白点则输出”Bad Request.”
5. QLen s t 询问 s 到 t 的路径上的白色最大权值和路径的最大长度,若
s 到 t 的路径上没有白点则输出 0
初始树上权值均为1,颜色均为白色。

输入格式

第一行一个整数n表示树的点数
接下来n−1行每行两个数s,t表示s,t有边相连
接下来一行一个数Q表示操作数
接下来Q行表示一个操作
n, Q ≤ 50000, val ≤ 1000

输出格式

对于每个 Qmax QLen 输出一行表示答案

样例

样例输入


			

6
1 2
2 4
2 5
1 3
3 6
7
CVal 1 0 5
CVal 1 1 3
CColor 1 0 1
CVal 2 0 5
CVal 3 0 3
QMax 5 6
QLen 5 6

样例输出


			
17
9

数据范围与提示