题解：「ROI 2023 Day2 T4」Выполнить план, но не перевыполнить（基于提供代码）

核心思路总览

本题通过 树形DP计算效率范围 + 区间构造计划 + 证书预计算 解决交互问题，核心逻辑是：

1. 用树形DP求出生产计划效率的最小值和最大值，以及中间所有可能的效率值。
2. 对每个查询的效率值 ( v_i )，判断是否在可行范围内，若可行则构造对应的生产计划并计算证书。
3. 交互阶段直接返回预存的计划或证书，确保响应效率。

整体复杂度 ( O(n + q\log n) )，适配 ( 2 \times 10^5 ) 规模数据。

关键步骤拆解

1. 树形DP计算效率范围

效率的本质是“树上带权最大独立集”（装配厂为独立集，权值为工厂人数）。通过两次DFS计算效率的可行范围：

（1）首次DFS（dfs1）：计算基础边界

• 对每个节点 ( x )，维护两个状态：
  • f[x][0]：不选 ( x ) 时，子树的最小效率（所有工厂取下限 ( L[i] )）。
  • f[x][1]：选 ( x ) 时，子树的最小效率。
  • g[x][0]：不选 ( x ) 时，子树的最大效率（所有工厂取上限 ( R[i] )）。
  • g[x][1]：选 ( x ) 时，子树的最大效率。
• 转移方程（以最小效率为例）：
  • f[x][0] += max(f[y][0], f[y][1])（不选当前节点，子节点可选或不选，取最大值）。
  • f[x][1] += f[y][0]（选当前节点，子节点必不选）。
• 同时记录节点的DFS序 dfn[x]，用于后续区间划分。

（2）二次DFS（dfs2）：计算中间效率值

• 调整根节点的状态，计算每个节点在“部分工厂取上限、部分取下限”时的效率值，存储在 val 数组中。
• val[i] 表示按DFS序前 ( i-1 ) 个节点取上限、其余取下限的效率，形成连续的效率范围。

2. 证书预计算（sl 和 sr 数组）

证书是异或和：( k = \bigoplus_{j=1}^n \left( (x \cdot j + y \cdot a_j^2) \bmod m \right) )。为快速计算任意计划的证书，预处理两个数组：

• sr[i]：前 ( i ) 个节点（按DFS序）取上限 ( R[j] ) 时的证书前缀异或和。
• sl[i]：第 ( i ) 到 ( n ) 个节点（按DFS序）取下限 ( L[j] ) 时的证书后缀异或和。
• 对于混合计划（前 ( p-1 ) 个上限，第 ( p ) 个中间值，其余下限），证书可通过 sr[p-2] ^ sl[p+1] ^ 中间值贡献 快速计算。

3. 查询处理与计划构造

（1）判断可行性

• 若查询的 ( v_i ) 小于最小效率 val[1] 或大于最大效率 val[n+1]，输出 -1。
• 否则，通过二分查找 val 数组，找到对应的位置 pos，确定需要调整的节点。

（2）构造计划与计算证书

• 当 pos=1 时：所有节点取下限 ( L[j] )，证书为 sl[1]。
• 当 pos>1 时：
  • 前 pos-2 个节点取上限 ( R[j] )。
  • 第 pos-1 个节点取中间值 now = R[w[pos-1]] - (val[pos] - v_i)（调整该节点使总效率为 ( v_i )）。
  • 其余节点取下限 ( L[j] )。
  • 证书通过 sr[pos-2] ^ sl[pos] ^ 中间值贡献 计算。

4. 交互检验响应

• 收到检验请求时，根据预存的构造逻辑，直接输出对应的计划（下限、上限或中间值），确保效率和证书匹配。

代码解析

1. 树形DP实现

• dfs1 递归计算每个节点的最小/最大效率，同时记录DFS序。
• dfs2 调整根节点状态，计算中间效率值 val，形成连续的可行效率范围。

2. 证书预处理

• sr 数组：从左到右累积上限节点的证书异或和。
• sl 数组：从右到左累积下限节点的证书异或和。

3. 查询响应

• 二分查找 val 数组定位效率值对应的调整位置。
• 按位置构造计划，通过前缀/后缀异或和快速计算证书。

4. 交互处理

• 检验阶段直接按构造逻辑输出计划，确保与第一阶段的证书一致。

关键验证（结合样例1）

• 样例1中所有工厂的人数固定（( L[i] = R[i] )），因此效率唯一。
• dfs1 计算出唯一效率值 19，val 数组中只有该值。
• 查询 ( v=19 ) 时，定位到对应位置，输出唯一计划的证书 10，检验时返回该计划。

复杂度分析

• 预处理：两次DFS均为 ( O(n) )，证书数组预处理 ( O(n) )，总 ( O(n) )。
• 查询：每个查询二分查找 ( O(\log n) )，总 ( O(q\log n) )。
• 交互检验：每次输出计划 ( O(n) )，但总次数受限（( n \cdot c \leq 10^6 )），不影响整体效率。

关键结论

本题的核心是利用树形DP确定效率的可行范围，通过区间划分构造中间效率的计划，并借助前缀/后缀异或和快速计算证书。交互阶段依赖预存的构造逻辑，确保响应正确高效。