题目分析

题目要求计算的是两点对 $(x, y)$ 的“距离”最大值，公式为：

$$\text{ans} = \max_{x, y} \{ \text{depth}(x) + \text{depth}(y) - \text{depth}(\text{LCA}(x, y)) - \text{depth}'(\text{LCA}'(x, y)) \} $$

其中 $\text{depth}$ 和 $\text{LCA}$ 对应树 $T$，$\text{depth}'$ 和 $\text{LCA}'$ 对应树 $T'$。

我们知道树上两点距离公式为 $\text{dist}_T(x, y) = \text{depth}(x) + \text{depth}(y) - 2 \cdot \text{depth}(\text{LCA}(x, y))$。 因此，可以将 $\text{depth}(\text{LCA}(x, y))$ 替换掉：

$$\text{depth}(\text{LCA}(x, y)) = \frac{\text{depth}(x) + \text{depth}(y) - \text{dist}_T(x, y)}{2} $$

代入原式并整理：

$$\text{val}(x, y) = \frac{1}{2} \left( \text{depth}(x) + \text{depth}(y) + \text{dist}_T(x, y) \right) - \text{depth}'(\text{LCA}'(x, y)) $$

为了消除分母，我们先计算 $2 \times \text{val}(x, y)$ 的最大值，最后除以 2。

$$2 \cdot \text{ans} = \max_{x, y} \{ (\text{depth}(x) + \text{depth}(y) + \text{dist}_T(x, y)) - 2 \cdot \text{depth}'(\text{LCA}'(x, y)) \} $$

算法设计

这是一个典型的“双树”问题。处理这类问题的通用套路是：第一棵树用边分治（或点分治），第二棵树用虚树（或动态树/线段树）。

1. 树 $T$ 的处理：边分治 (Edge Divide and Conquer)

为了方便处理 $\text{dist}_T(x, y)$，我们在树 $T$ 上进行边分治。

• 重构树：由于边分治在菊花图上复杂度会退化，我们需要先将多叉树转化为三度化的二叉树（添加虚点和权值为 0 的边）。这样可以保证分治层数为 $O(\log N)$。
• 分治过程：找到一条边 $(u, v)$ 将当前连通块分成两部分 $S_L$ 和 $S_R$。 对于跨越这条边的路径 $(x, y)$（其中 $x \in S_L, y \in S_R$），有：$$\text{dist}_T(x, y) = \text{dist}_T(x, u) + w(u, v) + \text{dist}_T(v, y) $$将上式代入目标公式，令 $W(p) = \text{depth}(p) + \text{dist}_T(p, \text{edge})$，则我们需要在 $T'$ 上最大化：$$(W(x) + W(y)) - 2 \cdot \text{depth}'(\text{LCA}'(x, y)) $$其中 $x$ 和 $y$ 分别属于不同的颜色集合（$S_L$ 染颜色 0，$S_R$ 染颜色 1）。

2. 树 $T'$ 的处理：虚树 + 树形 DP

在边分治的每一层，我们提取当前连通块内的所有节点，在树 $T'$ 上构建虚树。 在虚树上进行树形 DP 来求解跨颜色的最大值：

• 状态：dp[u][0/1] 表示在虚树节点 $u$ 的子树中，颜色为 0 或 1 的节点 $p$，其 $W(p)$ 的最大值。
• 转移：对于虚树上的每个节点 $u$（作为 $T'$ 上的 LCA），枚举其所有子节点 $v$，更新答案：$$\text{ans} = \max(\text{ans}, dp[u][0] + dp[v][1] - 2 \cdot \text{depth}'(u)) $$$$\text{ans} = \max(\text{ans}, dp[u][1] + dp[v][0] - 2 \cdot \text{depth}'(u)) $$更新完答案后，用子节点的信息更新 $u$ 的 $dp$ 值。

代码详解

代码主要分为两个命名空间：tree2 处理树 $T'$ 的虚树和 DP，tree1 处理树 $T$ 的重构和边分治。

1. namespace tree2 (树 $T'$)

• init(): 预处理 $T'$ 的 DFS 序、ST 表（用于 LCA），以及节点深度 dis。
• sol(vector<int> S): 对节点集合 $S$ 构建虚树。
  • 按 DFS 序排序。
  • 加入相邻节点的 LCA。
  • 构建虚树的边。
  • 调用 dfs2 进行 DP。
• dfs2(u): 树形 DP。
  • dp[u][col] 初始化为 w[u]（如果在集合中）。
  • 在回溯过程中，利用 max(dp[u][0] + dp[x][1], dp[u][1] + dp[x][0]) - 2 * dis[u] 更新全局答案 ans。
  • 注意公式对应：$W(x) + W(y) - 2 \text{depth}'(\text{LCA}')$。

2. namespace tree1 (树 $T$)

• reb(u, fa): 三度化重构。将原树的节点通过加入虚点变成二叉结构，保证边分治的复杂度。
• dfs2(u): 边分治主函数。
  • 找到重心边，断开。
  • work 函数计算当前连通块内所有节点到重心边的距离，并打上颜色标记（属于左侧还是右侧）。
  • 计算出每个点的权值 $W(p) = \text{depth}_T(p) + \text{dist}_T(p, \text{edge})$，存入 w[p]。
  • 将涉及到的节点传入 tree2::sol 进行计算。
  • 递归处理左右子树。

3. 主函数

• 读入两棵树的边。
• 调用 tree1::reb 重构 $T$。
• 调用 tree2::init 预处理 $T'$。
• 调用 tree1::dfs2 开始分治。
• 最终输出 ans / 2。

复杂度分析

• 重构树：$O(N)$。
• 边分治：递归深度 $O(\log N)$。
• 虚树构建与 DP：每一层分治中，所有节点都会被处理一次。虚树构建复杂度为 $O(K \log K)$（$K$ 为当前层节点数）。总复杂度为 $\sum O(K \log K) = O(N \log^2 N)$。
• ST 表构建：$O(N \log N)$。
• 总时间复杂度：$O(N \log^2 N)$。在 $N=366666$ 的数据下，4秒时限是足够的。