题目理解

我们有一棵 $n$ 个节点的树，每个节点 $i$ 有两个权值：

• $m_i$：日常活动人气
• $w_i$：聚会活动人气

每个节点有三种选择：

1. 日常活动：获得 $m_i$ 人气。
2. 聚会活动：获得 $w_i$ 人气，但必须满足以下条件之一：
   • 至少有一个相邻节点是后勤基地
   • 该节点到车站 $k$ 的距离 $\le L$
3. 后勤基地：人气为 $0$，但可以让相邻节点举办聚会。

目标：对于每个询问的 $L$，求最大可能的总人气。

---

问题转化

设最终总人气为所有节点的人气之和。我们需要在树上为每个节点分配合适的角色，使得聚会条件满足且总人气最大。

关键观察：

• 如果节点到 $k$ 的距离 $\le L$，它可以自由选择日常或聚会（不需要相邻后勤基地）
• 如果节点到 $k$ 的距离 $> L$，要举办聚会必须至少有一个邻居是后勤基地

---

核心思路：树上动态规划

状态设计

以车站 $k$ 为根进行 DFS，定义以下状态：

• dp1[u]：在 $u$ 的子树中，$u$ 可以举办聚会（即 $u$ 到根距离 $\le L$ 或 $u$ 的父亲是后勤基地）时的最大人气和
• dp2[u]：在 $u$ 的子树中，$u$ 不能举办聚会（即距离 $> L$ 且父亲不是后勤基地）时的最大人气和
• dp3[u]：在 $u$ 的子树中，$u$ 是后勤基地时的最大人气和
• dp4[u]：在 $u$ 的子树中，$u$ 可以举办聚会且父亲不是后勤基地时的最大人气和

状态转移

在 DFS 过程中计算：

• mx1：所有子节点 $v$ 的 dp1[v] 之和（所有子节点都可以聚会）
• mx12：所有子节点 $v$ 的 max(dp1[v], dp2[v]) 之和（子节点最佳状态）
• mx123：所有子节点 $v$ 的 max(dp1[v], dp2[v], dp3[v]) 之和（子节点任意状态）
• mx21：所有子节点 $v$ 的 dp2[v] - dp1[v] 的最大值

转移方程：

1. dp1[u]（$u$ 可以聚会）：

   • 日常活动：$m_u + mx12$
   • 聚会活动：$w_u + mx12 + \min(0, mx21)$
     这里 $\min(0, mx21)$ 表示：如果某个子节点在不能聚会时更优，就切换它到不能聚会状态，这样它必须成为后勤基地来满足 $u$ 聚会的条件

2. dp2[u]（$u$ 不能聚会）：

   • $mx123$，即 $u$ 任意状态（但不能聚会）下的最佳和

3. dp3[u]（$u$ 是后勤基地）：

   • $w_u + mx1$，这里 $u$ 聚会且子节点都可以聚会

4. dp4[u]（$u$ 可以聚会且父亲不是后勤基地）：

   • $\max(w_u, m_u) + mx12$

---

预处理与查询处理

预处理阶段

1. DFS 计算 DP 值：

   dfs1(k);  // 以 k 为根计算所有 DP 状态
   

2. 按深度分组：

   for (int i = 1; i <= n; i++) {
       nx2[i] = hd2[dep[i]];
       hd2[dep[i]] = i;
       suml[dep[i]] += max(m[i], w[i]);
   }
   

   计算前缀和 suml[d] 表示深度 $\le d$ 的所有节点取 $\max(m_i, w_i)$ 的和。

查询阶段

对于每个查询 $L$：

1. 深度 $\le L$ 的节点可以直接取 $\max(m_i, w_i)$（到车站距离 $\le L$，可以自由选择）
2. 深度 $= L+1$ 的节点需要特殊处理，用 DP 值 max(dp2[i], dp4[i]) 考虑它们能否通过相邻节点成为后勤基地来举办聚会
3. 深度 $> L+1$ 的节点在预处理时已通过 DP 考虑

查询公式：

ans = suml[l - 1];  // 深度 <= L 的节点
for (int i = hd2[l]; i != 0; i = nx2[i]) {
    ans += max(dp2[i], dp4[i]);  // 深度 = L+1 的节点
}

---

算法正确性分析

深度 $\le L$ 的节点：
由于到车站距离 $\le L$，它们可以自由选择日常或聚会，直接取 $\max(m_i, w_i)$ 是最优的。

深度 $= L+1$ 的节点：
这些节点到车站距离 $> L$，要举办聚会必须依赖相邻的后勤基地。通过 DP 值 max(dp2[i], dp4[i]) 可以准确计算在最优安排下这些节点的贡献。

深度 $> L+1$ 的节点：
在 DFS 过程中，它们的贡献已经通过子树的 DP 值被正确计算和传递到祖先节点。

---

时间复杂度分析

• 预处理：
  • DFS：$O(n)$
  • 按深度分组：$O(n)$
• 查询：
  • 平均 $O(1)$，最坏 $O(n)$，但通过记忆化 cc[l] 避免重复计算
• 总体：$O(n + q)$ 均摊

---

算法标签

• 树上动态规划
• 树形结构
• DFS
• 记忆化搜索
• 贪心思想

---

总结

本题的核心解法是：

1. 以车站为根建立树结构，利用深度信息判断节点能否直接举办聚会
2. 设计多状态树上 DP，精确处理不同约束条件下的最优选择
3. 按深度分组预处理，快速回答不同 $L$ 的查询
4. 记忆化优化，避免重复计算

这种解法巧妙地将"距离限制"和"相邻后勤基地"条件统一到 DP 状态设计中，通过一次 DFS 预处理所有可能需要的答案组件，从而高效支持多组查询。