F. Andrey's Tree 详解

题目理解

给定一棵 $n$ 个顶点的树。对于每个顶点 $v$（$1 \le v \le n$），考虑删除 $v$ 及其所有邻边后，剩下的图有若干个连通分量（每个分量是原树去掉 $v$ 后的一个子树）。我们需要通过添加若干条边（端点不能是 $v$），使得这些连通分量重新连通成一棵树，并且添加边的总代价 $\sum |a-b|$ 最小。输出最小代价和添加的边。

核心观察

1. 删除 $v$ 后的结构：

   • 设 $v$ 的度数为 $d$，删除 $v$ 后会得到 $d$ 个连通分量，每个分量对应 $v$ 的一个邻居的子树（如果原树以 $v$ 为根）。
   • 这些连通分量需要用 $d-1$ 条边连成一棵树（因为 $k$ 个分量需要 $k-1$ 条边连通）。

2. 代价的特殊性：

   • 边的代价是 $|a-b|$，即两端点编号之差的绝对值。
   • 这启发我们：尽量连接编号接近的点，以最小化代价。

3. 关键转化：

   • 每个连通分量对应一个编号区间（连续的一段整数）吗？不一定，但通过巧妙的 DFS 序和子树性质，我们可以发现：
   • 在原树中，每个子树（删除 $v$ 后得到的连通块）对应的顶点编号集合在数值上不一定连续，但可以通过对 DFS 序的处理，找到每个连通块在编号轴上的“最小”和“最大”邻居。

算法思路（对标程的分析）

标程的核心思想：对于每个 $v$，在其邻居对应的连通块之间，用“相邻编号”的点来连接，从而最小化代价。

第一步：DFS 预处理

vector<int> tin(n), tout(n), l0(n), r0(n);
vector<int> lup(n), rup(n);

• tin[v], tout[v]：DFS 进入和离开时间戳。
• l0[v], r0[v]：以 $v$ 为根的子树中，顶点编号的最小值和最大值。
• lup[v], rup[v]：补集的最小/最大编号，即不在 $v$ 的子树中的顶点编号的最小值和最大值。

这些信息可以通过一次 DFS 和前后缀预处理得到。

第二步：处理删除 $v$ 后的连通块

删除 $v$ 后，连通块有：

• $v$ 的每个子节点 $u$ 对应的子树（编号范围 [l0[u], r0[u]]）
• 如果 $v$ 不是根，还有一个“上方”的连通块（编号范围 [lup[v], rup[v]]）

第三步：贪心连接（核心）

对于每个连通块，我们找到它在编号轴上紧邻的左右邻居（即该块的最小编号减 1，最大编号加 1），并尝试在这些邻居之间加边。

具体地，对每个邻居 $u$ 对应的块：

• 尝试连接 l0[u] - 1 和 l0[u]（如果存在）
• 尝试连接 r0[u] 和 r0[u] + 1（如果存在）

对于“上方”块：

• 尝试连接 lup[v] - 1 和 lup[v]
• 尝试连接 rup[v] 和 rup[v] + 1

这样做的原因是：为了用最小代价连通所有块，最优策略是沿着编号轴“相邻”连接，类似用 $d-1$ 条边将 $d$ 个区间串起来。

第四步：并查集维护连通性

使用并查集维护 $v$ 的各个邻居对应的连通块（用它们在邻接表中的索引表示）。每次尝试加边时，如果连接的两个点属于不同块，就合并它们，并记录这条边。

最终需要 $d-1$ 条边，如果不足，再尝试连接 v-1 和 v+1（兜底）。

关键函数解析

get_subtree(u)

function<int(int)> get_subtree = [&](int u) {
    if (!ancestor(v, u)) return idpar;
    return all_id[upper_bound(all_tin.begin(), all_tin.end(), tin[u]) - all_tin.begin() - 1];
};

• 给定一个顶点 $u$（$u \ne v$），返回 $u$ 属于 $v$ 的哪个邻居的子树。
• 如果 $u$ 不在 $v$ 的子树中（即 $u$ 在上方），返回父边对应的索引 idpar。
• 否则，根据 DFS 序二分找到 $u$ 属于哪个子节点。

try_add(x, y)

function<void(int, int)> try_add = [&](int x, int y) {
    if (x == -1 || y == n || x == v || y == v) return;
    if (dsu.join(get_subtree(x), get_subtree(y))) {
        ans[v].push_back({x, y});
        weight[v] += abs(x - y);
    }
};

• 尝试在 $x$ 和 $y$ 之间加边。
• 检查端点是否有效（$0 \le x,y < n$，且不等于 $v$）。
• 如果它们属于不同的连通块，则添加这条边，并合并块。

复杂度分析

• DFS 预处理：$O(n)$
• 对每个 $v$：处理其所有邻居，每个邻居尝试 $O(1)$ 次加边，并查集操作近似 $O(\alpha(n))$。
• 总复杂度：$O(n \cdot \text{deg}(v)) = O(n)$ 均摊（因为每条边在两侧各考虑一次）。

示例验证（第一个测试用例）

输入：

5
1 3
1 4
4 5
3 2

以 $v=4$ 为例（注意代码中顶点编号从 0 开始）：

• 删除 4 后，连通块：{3,2,1} 和 {5}（因为 4 连接 1 和 5）
• 编号轴：块1 包含 {1,2,3}（连续？实际 1,2,3 连续），块2 包含 {5}
• 最优加边：连接 3 和 5（块1 的最大编号 3 与块2 的 5 相邻？实际是 3 和 5 差 2，但标程会尝试 r0[5]=5 与 r0[5]+1=6（无效），以及 l0[1]=1 与 l0[1]-1=0（无效），可能需要兜底逻辑）
• 实际输出中 $v=4$ 对应的输出是：

  1 1
  3 4
  

  即加边 (3,4)（转换为 1-indexed 后为 (3,4)），代价 1。这与题目描述（加边 5 到 3，代价 2）不同？注意题目输出中 $v=4$ 对应的是 1 1 和 3 4，确实代价为 $|3-4|=1$，比示例说明的更优。这说明标程找到了更优解。

总结

标程的核心思想是：

1. 预处理每个子树的最小/最大编号，以及补集的最小/最大编号。
2. 对于删除 $v$ 后的每个连通块，尝试用其边界上的编号与相邻编号的点加边。
3. 使用并查集维护连通性，保证添加的边恰好 $d-1$ 条，且总代价最小。

这种方法利用了编号差的绝对值这一特殊代价函数，将问题转化为在编号轴上连接相邻区间，从而得到最优解。