#2814. tree

内存限制:512 MiB 时间限制:5 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<=5W,Q<=5W,1<=val<=1K,0<=color,layer<=1 所有数据不超过longint范围。 .

输入格式

第一行一个数N,接下来N*2-2个数s,t,代表s与t之间有连边。第N+1行一个数Q,表示操作数。接下来Q行每行一个操作。

输出格式

对于每次 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

数据范围与提示