F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5081. -- 树

5081: 树

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 58  Solved: 1
[Submit][Status][Discuss]

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,颜色均为白色。

Input

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

Output

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

Sample Input


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

Sample Output

17
9

HINT

Source

[Submit][Status][Discuss]

HOME Back