#P5081. 树

    ID: 4168 传统题 5000ms 512MiB 尝试: 60 已通过: 1 难度: 10 上传者: 标签>难度分类省选/NOI-树算法树链剖分数据结构懒标记线段树动态规划插头 DP插头连通性编码轮廓状态规范化普通并查集模拟与实现技巧预计算转移构造与建模多目标整数权值编码CF3000

树

P5081 树

题目描述

给定一棵有 nn 个结点的树。每个结点分为 第 00 层和第 11 层,每层分别有一个权值和一种颜色(白色或黑色)。初始时所有层的权值都为 11,颜色都为白色。

支持以下五种操作:

  1. Cover s t color:把树上从 ss 到 tt 的简单路径所经过结点的两层颜色全部设为 color(0 为白色,1 为黑色)。
  2. CVal index layer val:把结点 index 的第 layer 层权值修改为 val。
  3. CColor index layer color:把结点 index 的第 layer 层颜色修改为 color。
  4. QMax s t:只考虑原树上 ss 到 tt 的简单路径上的结点,求其中一条完全由白色层组成的合法路径的最大权值和。如果不存在白色层,输出 Bad Request.。
  5. QLen s t:对于同样的查询范围,求权值和达到最大值的合法白色路径所能具有的最大长度(经过的层数)。如果不存在白色层,输出 0。

合法路径的移动规则:

  • 可以在同一结点的第 00 层和第 11 层之间移动;
  • 也可以在原树中相邻结点的同一层之间移动;
  • 经过的每一层必须是白色;
  • 每个「结点、层」组成的状态最多经过一次;
  • 路径的起点、终点可以是查询范围内任意白色层,不必是 ss、tt 对应的层。

一条路径的权值和是所经过各层权值之和;长度是所经过的层数(不是移动次数)。

输入格式

从标准输入读入。第一行一个整数 nn,表示树中结点数。

接下来 n−1n-1 行,每行两个整数 s,ts,t,表示树上有一条连接 s,ts,t 的无向边。

接下来一行一个整数 QQ,表示操作数量。

接下来 QQ 行,每行一个操作,格式为上述五种命令之一。

输出格式

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

数据范围

对于全部数据:

  • 1≤n≤500001\le n\le 50000;
  • 1≤Q≤500001\le Q\le 50000;
  • 点编号为 1∼n1\sim n;
  • 层编号 layer 取 0 或 1;
  • 颜色编号 color 取 0 或 1;
  • 权值更新参数满足 val≤1000val\le1000。