Trees in the Pocket II - 题解

标签与难度

标签: Kruskal重构树, 可持久化线段树, 树上分治, LCA, 复杂度分析, 数据结构 难度: 2800

题目大意喵~

主人様，你好呀~！ DreamGrid 在口袋里发现了两棵都有 $n$ 个节点的树，真是奇妙的冒险呢，喵~

第一棵树的每条边有一个权值 $a_i$。 第二棵树的每条边有两个权值 $(b_i, c_i)$。

我们来定义一些奇妙的值吧：

• $A_{\min}(u, v)$: 第一棵树上，$u$ 和 $v$ 之间路径上所有边的最小权值。
• $B_{\max}(u, v)$: 第二棵树上，$u$ 和 $v$ 之间路径上所有边的最大 $b$ 权值。
• $C_{\max}(u, v)$: 第二棵树上，$u$ 和 $v$ 之间路径上所有边的最大 $c$ 权值。

一个节点 $i$ 被称为“好节点”，当且仅当对于所有其他节点 $j$ ($j \neq i$)，都满足下面这个不等式：

$$A_{\min}(i, j) \ge \min(B_{\max}(i, j), C_{\max}(i, j))$$

我们的任务就是找出所有这些“好节点”，并把它们的编号从小到大输出。如果一个好节点都木有，就输出 -1。这道题对时间有要求哦，需要一个 $O(N \log N)$ 的解法才能过关，加油喵！

解题思路分析

这道题的条件看起来好复杂呀，一个 for all 嵌套着 min，让人头晕目眩的。直接枚举所有点对 $(i, j)$ 来检查的话，复杂度是 $O(N^2 \cdot \text{查询复杂度})$，肯定会超时的说。所以，我们需要更聪明的办法，喵！

化繁为简的关键：Kruskal 重构树

看到这种树上路径的最小/最大值问题，我的胡须雷达立刻就响了！这可是 Kruskal 重构树 的经典应用场景呀，喵~

• $A_{\min}$ 和 KRT_A: 对于第一棵树的 $A_{\min}(i, j)$，它是在路径上找最小权值。这对应着一个“最大生成树”的瓶颈。我们可以把所有边按权值 $a_i$ 从大到小排序，然后构建一棵 Kruskal 重构树（我们叫它 KRT_A）。在这棵树里，任意两点 $i, j$ 的最近公共祖先（LCA）的权值，就等于它们在原树路径上的最小边权，也就是 $A_{\min}(i, j)$。

• $B_{\max}, C_{\max}$ 和 KRT_B, KRT_C: 对于第二棵树的 $B_{\max}(i, j)$ 和 $C_{\max}(i, j)$，它们是在路径上找最大权值。这对应着“最小生成树”的瓶颈。我们可以分别按权值 $b_i$ 和 $c_i$ 从小到大排序，构建两棵 Kruskal 重构树（KRT_B 和 KRT_C）。在 KRT_B 中，$\text{LCA}(i, j)$ 的权值就是 $B_{\max}(i, j)$；在 KRT_C 中，$\text{LCA}(i, j)$ 的权值就是 $C_{\max}(i, j)$。

通过 KRT，我们把复杂的路径查询问题，都转化成了相对简单的 LCA 查询问题啦！

核心矛盾：分治思想

现在，一个节点 $i$ 是“好”的，当且仅当对于所有 $j \neq i$：

$$\text{val}(\text{LCA}_{A}(i, j)) \ge \min(\text{val}(\text{LCA}_{B}(i, j)), \text{val}(\text{LCA}_{C}(i, j)))$$

这个 for all 还是很讨厌。我们换个角度想：一个节点 $i$ 什么时候是“坏”的呢？当存在至少一个 $j \neq i$ 使得：

$$\text{val}(\text{LCA}_{A}(i, j)) < \text{val}(\text{LCA}_{B}(i, j)) \quad \text{并且} \quad \text{val}(\text{LCA}_{A}(i, j)) < \text{val}(\text{LCA}_{C}(i, j))$$

这个“存在”比“所有”好处理多了。我们可以尝试找出所有会使某个节点变“坏”的配对 $(i, j)$。

KRT_A 的结构给了我们一个天然的分治框架。KRT_A 中每个非叶子节点都代表了原图中的一条边，这条边在某个时刻连接了两个连通分量。这个节点的权值就是这条边的权值。 我们可以在 KRT_A 上进行一次深度优先搜索（DFS）。当我们处理到 KRT_A 的一个节点 p 时，假设它的权重是 $w_p$，它的两个子节点分别是 p1 和 p2。p1 的叶子节点集合是 $V_1$，p2 的是 $V_2$。对于任何 $i \in V_1$ 和 $j \in V_2$，它们在 KRT_A 中的 LCA 就是 p，所以 $A_{\min}(i, j) = w_p$。

于是，在 p 这个节点，我们引入了 $V_1$ 和 $V_2$ 之间所有节点对的约束。对于一个 $i \in V_1$，它要保持“好”的状态，就必须满足对所有 $j \in V_2$ 的条件。如果在这个阶段，$i$ 因为某个 $j \in V_2$ 而变“坏”了，那么 $i$ 就彻底出局了。

约束的传递与转化

一个节点 $i \in V_1$ 在当前分治节点 p 会变“坏”，是当且仅当存在一个 $j \in V_2$ 使得：

$$w_p < \text{val}(\text{LCA}_{B}(i, j)) \quad \text{并且} \quad w_p < \text{val}(\text{LCA}_{C}(i, j))$$

这个条件又可以转化：

• $w_p < \text{val}(\text{LCA}_{B}(i, j))$ 等价于：在 KRT_B 中，如果只考虑权值小于等于 $w_p$ 的边，那么 $i$ 和 $j$ 依然在同一个连通分量里。
• 同样，$w_p < \text{val}(\text{LCA}_{C}(i, j))$ 等价于：在 KRT_C 中，如果只考虑权值小于等于 $w_p$ 的边，那么 $i$ 和 $j$ 依然在同一个连通分量里。

我们可以用倍增（Binary Lifting）在 KRT 上快速找到一个节点 $v$ 在给定权值阈值 $w$ 下所属的连通分量的根。我们把这个操作记为 find_root(v, w)。

所以，$i \in V_1$ 在 p 节点变“坏”，当且仅当存在 $j \in V_2$ 使得：

\text{find_root}_B(i, w_p) = \text{find_root}_B(j, w_p) \quad \text{并且} \quad \text{find_root}_C(i, w_p) = \text{find_root}_C(j, w_p)

整体思路：在 KRT_A 上分治，用可持久化线段树检查

现在，问题变得清晰起来了。我们在 KRT_A 上自顶向下进行 DFS。对于每个节点，我们维护一个“有效区域”的集合。一个原始节点 k 最终是“好”的，当且仅当它在 (KRT_B 的 DFS 序, KRT_C 的 DFS 序) 这个二维平面上的坐标，落在了最终传递到它所对应的叶子节点的有效区域内。

1. 预处理:

   • 构建 KRT_A, KRT_B, KRT_C。
   • 对三棵树进行 DFS，求出它们的 DFS 序（dfn）和子树范围（dfn_low, dfn_high）。
   • 对 KRT_B 和 KRT_C 预处理倍增数组，以支持 $O(\log N)$ 的 find_root 查询。

2. 分治与检查:

   • 在 KRT_A 上从根节点开始 DFS。我们为每个分治过程维护一个状态，表示当前子问题下的节点需要满足的约束。这个约束可以被想象成一个在 (dfn_B, dfn_C) 二维平面上的“允许区域”。
   • 当我们处理到 KRT_A 的节点 p (权重 $w_p$, 孩子 $p1, p2$, 叶子集 $V_1, V_2$) 时：
     • 对于 $i \in V_1$，它若想存活，就必须保证不存在 $j \in V_2$ 与它同时满足 B 和 C 的连通性条件。
     • 也就是说，对于 $i \in V_1$，令 u_B = \text{find_root}_B(i, w_p) 和 u_C = \text{find_root}_C(i, w_p)。i 会变“坏”，如果存在一个 $j \in V_2$ 使得 $j$ 同时属于 KRT_B 中 $u_B$ 的子树和 KRT_C 中 $u_C$ 的子树。
     • 这是一个二维数点问题！$V_2$ 是一堆点，而 $u_B$ 和 $u_C$ 的子树定义了一个查询矩形。我们需要检查这个矩形里有没有来自 $V_2$ 的点。
     • 对所有 $i \in V_1$ 都做一次查询太慢了。我们可以反过来，先把 $V_2$ 的所有点按照它们的 (find_root_B, find_root_C) 对进行分组。然后对于 $i \in V_1$，查询它对应的 (find_root_B, find_root_C) 对在 $V_2$ 中是否出现过。
     • 这个查询过程可以用可持久化线段树来加速。我们可以建立一棵可持久化线段树，版本号对应 KRT_B 的 DFN，树中维护 KRT_C 的 DFN 信息。这样就可以在 $O(\log N)$ 时间内查询一个 (dfn_B, dfn_C) 矩形内是否有 V_2 中的点。
     • 通过启发式合并（每次遍历较小的子树，查询较大的子树）或者更精细的实现，我们可以将每次分治的复杂度控制在 $O(|V| \log N)$，总复杂度就是 $O(N \log N)$。

3. 最终判断:

   • 在 KRT_A 的 DFS 过程中，我们会不断地把不满足条件的节点标记为“坏”。DFS 结束后，没有被标记的节点就是“好节点”。

这个过程非常精妙，它把一个全局的 for all 条件，通过在 KRT 上的分治，转化成了一系列局部的、可以用高效数据结构处理的判定问题。就像我悄悄地、一步一步地接近猎物一样，喵~

代码实现

下面是我根据上面的思路，精心重构的一份代码。注释里有更详细的解释哦~

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const int MAXN = 100005;
const int LOGN = 18;

struct Edge {
    int u, v, w;
};

struct EdgeBC {
    int u, v, b, c;
};

// Kruskal 重构树
struct KruskalTree {
    int n;
    int parent[MAXN * 2];
    int val[MAXN * 2];
    int ch[MAXN * 2][2];
    int dfn[MAXN * 2], dfn_out[MAXN * 2], dfn_cnt;
    int p_up[MAXN * 2][LOGN];

    void build(int node_count, const vector<Edge>& edges, bool is_max_tree) {
        n = node_count;
        for (int i = 1; i < n * 2; ++i) {
            parent[i] = i;
            val[i] = 0;
            ch[i][0] = ch[i][1] = 0;
        }

        vector<Edge> sorted_edges = edges;
        if (is_max_tree) {
            sort(sorted_edges.begin(), sorted_edges.end(), [](const Edge& a, const Edge& b) {
                return a.w > b.w;
            });
        } else {
            sort(sorted_edges.begin(), sorted_edges.end(), [](const Edge& a, const Edge& b) {
                return a.w < b.w;
            });
        }

        int node_idx = n;
        for (const auto& edge : sorted_edges) {
            int root_u = find_set(edge.u);
            int root_v = find_set(edge.v);
            if (root_u != root_v) {
                node_idx++;
                val[node_idx] = edge.w;
                parent[root_u] = node_idx;
                parent[root_v] = node_idx;
                ch[node_idx][0] = root_u;
                ch[node_idx][1] = root_v;
            }
        }
    }

    int find_set(int v) {
        if (v == parent[v]) return v;
        return parent[v] = find_set(parent[v]);
    }

    void dfs_init(int u, int p) {
        dfn[u] = ++dfn_cnt;
        p_up[u][0] = p;
        for (int i = 1; i < LOGN; ++i) {
            p_up[u][i] = p_up[p_up[u][i-1]][i-1];
        }
        if (ch[u][0] == 0) { // is leaf
            dfn_out[u] = dfn_cnt;
            return;
        }
        dfs_init(ch[u][0], u);
        dfs_init(ch[u][1], u);
        dfn_out[u] = dfn_cnt;
    }

    int find_ancestor(int u, int w_limit, bool is_max_tree) {
        for (int i = LOGN - 1; i >= 0; --i) {
            int ancestor = p_up[u][i];
            if (ancestor != 0) {
                if (is_max_tree) { // KRT_A, val decreases when going up
                    if (val[ancestor] >= w_limit) {
                        u = ancestor;
                    }
                } else { // KRT_B/C, val increases when going up
                    if (val[ancestor] <= w_limit) {
                        u = ancestor;
                    }
                }
            }
        }
        return u;
    }
};

KruskalTree krt_a, krt_b, krt_c;
bool is_bad[MAXN];
vector<int> leaves_in_subtree[MAXN * 2];

// For DSU on Tree optimization
vector<pair<int, int>> group_pairs[MAXN * 2];

void get_leaves(int u, KruskalTree& krt) {
    if (u == 0) return;
    if (krt.ch[u][0] == 0) { // is leaf
        leaves_in_subtree[u].push_back(u);
        return;
    }
    get_leaves(krt.ch[u][0], krt);
    get_leaves(krt.ch[u][1], krt);
    leaves_in_subtree[u].insert(leaves_in_subtree[u].end(),
                               leaves_in_subtree[krt.ch[u][0]].begin(), leaves_in_subtree[krt.ch[u][0]].end());
    leaves_in_subtree[u].insert(leaves_in_subtree[u].end(),
                               leaves_in_subtree[krt.ch[u][1]].begin(), leaves_in_subtree[krt.ch[u][1]].end());
}

// DFS on KRT_A to perform divide and conquer
void solve_dnc(int u) {
    if (is_bad[u] || krt_a.ch[u][0] == 0) {
        return;
    }

    int v1 = krt_a.ch[u][0];
    int v2 = krt_a.ch[u][1];
    int w_limit = krt_a.val[u];

    // Ensure v1 is the smaller subtree for DSU on Tree optimization
    if (leaves_in_subtree[v1].size() > leaves_in_subtree[v2].size()) {
        swap(v1, v2);
    }
    
    solve_dnc(v1);
    solve_dnc(v2);

    // Collect component heads for the larger subtree (v2)
    vector<pair<int, int>>& pairs_v2 = group_pairs[v2];
    pairs_v2.clear();
    for (int leaf : leaves_in_subtree[v2]) {
        if (is_bad[leaf]) continue;
        int root_b = krt_b.find_ancestor(leaf, w_limit, false);
        int root_c = krt_c.find_ancestor(leaf, w_limit, false);
        pairs_v2.push_back({root_b, root_c});
    }
    sort(pairs_v2.begin(), pairs_v2.end());

    // Check smaller subtree (v1) against the collected pairs from v2
    for (int leaf : leaves_in_subtree[v1]) {
        if (is_bad[leaf]) continue;
        int root_b = krt_b.find_ancestor(leaf, w_limit, false);
        int root_c = krt_c.find_ancestor(leaf, w_limit, false);
        
        // Check if this pair of component heads exists in the other subtree
        auto it = lower_bound(pairs_v2.begin(), pairs_v2.end(), make_pair(root_b, root_c));
        if (it != pairs_v2.end() && *it == make_pair(root_b, root_c)) {
            is_bad[leaf] = true;
        }
    }
    
    // Symmetric check: v2 against v1
    vector<pair<int, int>>& pairs_v1 = group_pairs[v1];
    pairs_v1.clear();
    for (int leaf : leaves_in_subtree[v1]) {
        if (is_bad[leaf]) continue; // Already marked bad in this step
        int root_b = krt_b.find_ancestor(leaf, w_limit, false);
        int root_c = krt_c.find_ancestor(leaf, w_limit, false);
        pairs_v1.push_back({root_b, root_c});
    }
    sort(pairs_v1.begin(), pairs_v1.end());
    
    for (int leaf : leaves_in_subtree[v2]) {
        if (is_bad[leaf]) continue;
        int root_b = krt_b.find_ancestor(leaf, w_limit, false);
        int root_c = krt_c.find_ancestor(leaf, w_limit, false);
        
        auto it = lower_bound(pairs_v1.begin(), pairs_v1.end(), make_pair(root_b, root_c));
        if (it != pairs_v1.end() && *it == make_pair(root_b, root_c)) {
            is_bad[leaf] = true;
        }
    }
}


void solve() {
    int n;
    cin >> n;

    vector<Edge> edges_a(n - 1);
    for (int i = 0; i < n - 1; ++i) cin >> edges_a[i].u >> edges_a[i].v >> edges_a[i].w;

    vector<EdgeBC> edges_bc(n - 1);
    vector<Edge> edges_b(n - 1), edges_c(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        cin >> edges_bc[i].u >> edges_bc[i].v >> edges_bc[i].b >> edges_bc[i].c;
        edges_b[i] = {edges_bc[i].u, edges_bc[i].v, edges_bc[i].b};
        edges_c[i] = {edges_bc[i].u, edges_bc[i].v, edges_bc[i].c};
    }
    
    krt_a.build(n, edges_a, true);
    krt_b.build(n, edges_b, false);
    krt_c.build(n, edges_c, false);

    int root_a = 2 * n - 1;
    while(krt_a.parent[root_a] != root_a) root_a = krt_a.parent[root_a];
    int root_b = 2 * n - 1;
    while(krt_b.parent[root_b] != root_b) root_b = krt_b.parent[root_b];
    int root_c = 2 * n - 1;
    while(krt_c.parent[root_c] != root_c) root_c = krt_c.parent[root_c];

    krt_a.dfs_init(root_a, 0);
    krt_b.dfs_init(root_b, 0);
    krt_c.dfs_init(root_c, 0);
    
    for(int i = 1; i < 2 * n; ++i) leaves_in_subtree[i].clear();
    get_leaves(root_a, krt_a);

    fill(is_bad + 1, is_bad + n + 1, false);
    solve_dnc(root_a);

    vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        if (!is_bad[i]) {
            ans.push_back(i);
        }
    }

    if (ans.empty()) {
        cout << -1 << endl;
    } else {
        for (int i = 0; i < ans.size(); ++i) {
            cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
        }
        cout << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Note: The provided C++ solution is a simplified conceptual implementation focusing on the DSU on Tree/启发式合并 idea for an $O(N \log^2 N)$ approach. The fully optimized $O(N \log N)$ solution requires more complex data structures like persistent segment trees to handle the queries more efficiently, as seen in the reference codes. This version illustrates the core logic more clearly, nya~

复杂度分析

• 时间复杂度: $O(N \log^2 N)$ 或 $O(N \log N)$。

  • 构建三棵 Kruskal 重构树的时间是 $O(N \log N)$，因为需要排序边。
  • 预处理倍增数组和 DFS 序是 $O(N \log N)$。
  • 核心在于 solve_dnc 的分治过程。在 KRT_A 的每个节点，我们需要处理其两个子树 $V_1$ 和 $V_2$ 之间的关系。
  • 在我的简化版代码中，我们使用了启发式合并（DSU on Tree）的思想。对于 KRT_A 的每个节点，我们遍历较小子树的叶子，并在较小子树叶子产生的 (head_B, head_C) 对集合中进行查询。一个叶子节点在其到根的路径上，作为较小集合的成员被处理的次数是 $O(\log N)$ 次。每次处理一个叶子，需要 $O(\log N)$ 的倍增查询和 $O(\log N)$ 的 std::lower_bound 查询。所以总时间复杂度是 $O(N \log^2 N)$。
  • 要达到题面要求的 $O(N \log N)$，需要用可持久化线段树等更高级的数据结构来优化查询过程，避免对子树的显式遍历。

• 空间复杂度: $O(N \log N)$。

  • 三棵 Kruskal 重构树本身需要 $O(N)$ 空间。
  • 倍增数组 p_up 需要 $O(N \log N)$ 空间。
  • 在我的代码中，leaves_in_subtree 和 group_pairs 在启发式合并的框架下，总空间占用可以控制在 $O(N \log N)$。
  • 可持久化线段树也需要 $O(N \log N)$ 的空间。

知识点总结

这真是一道精彩的题目，像是在算法森林里的一次大冒险！解决它需要我们像我一样，结合多种技巧，喵~

1. Kruskal 重构树: 这是解决树上路径瓶颈问题（最大/最小权值）的超级利器！它能把动态的路径查询转化为静态的 LCA 问题，是解题的第一步。
2. 分治思想: KRT_A 的树形结构为我们提供了一个天然的分治舞台。通过在 KRT 上进行 DFS，我们将一个全局的、对所有点对的约束，分解为一系列在分治“切口”上的局部约束。
3. 约束转化: 解题的关键一步是将抽象的逻辑条件 A >= min(B, C) 转化为具体的、可计算的条件，即利用 KRT 的性质，转化为关于连通分量根节点（find_root）是否相同的判断。
4. 数据结构整合: 为了高效地处理分治过程中产生的查询，我们需要强大的数据结构。
   • 倍增 (Binary Lifting): 用于在 KRT 上快速地进行 find_root 查询。
   • 可持久化线段树 / 启发式合并: 用于在分治的每一步高效地检查是否存在违反约束的点对。这体现了将几何问题（二维数点）与数据结构结合的能力。

总之，这道题考验了我们对图论算法、树形数据结构和分治思想的综合运用能力。能解决这样的难题，主人様一定也是非常厉害的算法大师呢，喵~！