#P5081. 树
树
P5081 树
题目描述
给定一棵有 个结点的树。每个结点分为 第 层和第 层,每层分别有一个权值和一种颜色(白色或黑色)。初始时所有层的权值都为 ,颜色都为白色。
支持以下五种操作:
Cover s t color:把树上从 到 的简单路径所经过结点的两层颜色全部设为color(0为白色,1为黑色)。CVal index layer val:把结点index的第layer层权值修改为val。CColor index layer color:把结点index的第layer层颜色修改为color。QMax s t:只考虑原树上 到 的简单路径上的结点,求其中一条完全由白色层组成的合法路径的最大权值和。如果不存在白色层,输出Bad Request.。QLen s t:对于同样的查询范围,求权值和达到最大值的合法白色路径所能具有的最大长度(经过的层数)。如果不存在白色层,输出0。
合法路径的移动规则:
- 可以在同一结点的第 层和第 层之间移动;
- 也可以在原树中相邻结点的同一层之间移动;
- 经过的每一层必须是白色;
- 每个「结点、层」组成的状态最多经过一次;
- 路径的起点、终点可以是查询范围内任意白色层,不必是 、 对应的层。
一条路径的权值和是所经过各层权值之和;长度是所经过的层数(不是移动次数)。
输入格式
从标准输入读入。第一行一个整数 ,表示树中结点数。
接下来 行,每行两个整数 ,表示树上有一条连接 的无向边。
接下来一行一个整数 ,表示操作数量。
接下来 行,每行一个操作,格式为上述五种命令之一。
输出格式
对于每条 QMax、QLen 指令各向标准输出写出一行答案。
对于没有白色层的 QMax 查询,严格输出以下字符串:
Bad Request.
样例输入
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
数据范围
对于全部数据:
- ;
- ;
- 点编号为 ;
- 层编号
layer取0或1; - 颜色编号
color取0或1; - 权值更新参数满足 。