6814: BZOJ2814:tree

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给出一棵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

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: