Graph - 题解

标签与难度

标签: 图论, 最小生成树, 异或(XOR), Trie树, 分治, 势能分析难度: 2200

题目大意喵~

你好呀，未来的算法大师！本喵今天带来了一道关于图的有趣问题，喵~

题目是这样的：我们有一个由 $N$ 个顶点和 $N-1$ 条边组成的连通图。哇，这不就是一棵树嘛！每条边都有一个“丑陋值”（ugly value）。我们可以进行任意次数的操作，每次操作可以添加或删除一条带有丑陋值的边。

但是，在任何时候，图都必须满足两个条件哦：

图必须是连通的。
对于图中存在的任意一个环，环上所有边的丑陋值的异或和必须为 0。

我们的目标是，在满足这两个条件的前提下，让最终图中所有边的丑陋值之和最小。请你求出这个最小的总和是多少，呐。

解题思路分析

这道题看起来有点复杂，又是连通，又是环的异或和为0，还要总和最小...别怕别怕，让本喵来帮你一步步解开它的神秘面纱，喵~

关键条件：环的异或和为 0

我们先来研究一下这个最特别的条件：“任意环的异或和为 0”。这其实是一个非常经典的性质，它告诉我们一个深刻的秘密！

想象一下，从某个顶点 u 到另一个顶点 v，如果存在两条不同的路径，那么这两条路径就构成了一个环。设路径1上所有边的异或和是 $P_1$ ，路径2上所有边的异或和是 $P_2$ 。这个环的总异或和就是 $P_1 \oplus P_2$ （ $\oplus$ 是异或符号哦）。

题目要求 $P_1 \oplus P_2 = 0$ ，这等价于 $P_1 = P_2$ ！

这意味着，在满足条件的图中，从任意顶点 u 到任意顶点 v，所有可能路径的边权异或和都是相等的。

这个性质太棒了！它允许我们为每个顶点定义一个“势”（potential）。我们可以选定一个起始点（比如说，顶点1），并规定它的势 $potential_1 = 0$ 。对于其他任何顶点 u，它的势 $potential_u$ 就定义为从顶点1到顶点u的路径异或和。因为这个值是唯一的，所以这个定义是明确的。

那么，一条边 $(u, v)$ 的权值 $w$ 和它两端顶点的势有什么关系呢？从 1 到 v 的路径可以看作是“从 1 到 u”，再“从 u 到 v”。所以，它们的势满足关系： $potential_v = potential_u \oplus w$ 两边同时异或 $potential_u$ ，我们得到： $w = potential_u \oplus potential_v$

哇！也就是说，只要我们为每个顶点 $i$ 确定了一个势值 $p_i$ ，那么任意一条边 $(u, v)$ 的权值就必须是 $p_u \oplus p_v$ 。

问题的转化

现在，问题变得清晰多啦！

第一步：计算初始势 题目给定的初始图是一棵树。我们正好可以利用它来计算出一组符合条件的势。我们任选一个根节点（比如题目中的0号顶点，我们这里用1号），设 $p_1 = 0$ 。然后从根节点开始进行一次深度优先搜索（DFS），对于一条边 $(u, v)$ ，如果 $u$ 是 $v$ 的父节点，那么 $v$ 的势就是 $p_v = p_u \oplus w_{uv}$ 。这样我们就能计算出所有 $N$ 个顶点的初始势值，我们记作 $d_1, d_2, \dots, d_N$ 。
第二步：构建新图并求最小生成树 我们现在有了一组“魔法数字”（势） $d_1, \dots, d_N$ 。我们的任务是，用这些点构建一个连通图，使得边权总和最小。边的权值必须遵循 $w_{uv} = d_u \oplus d_v$ 的规则。为了让一个有 $N$ 个顶点的图连通且总权值最小，我们应该怎么做呢？当然是求它的最小生成树 (MST) 啦！所以，问题最终转化为：
给定 $N$ 个数 $d_1, d_2, \dots, d_N$ 。想象一个完全图，其中任意两点 $i$ 和 $j$ 之间的边权为 $d_i \oplus d_j$ 。求这个完全图的最小生成树的总权值。

高效求解 XOR-MST

在一个有 $N$ 个顶点的完全图上跑传统的 Kruskal 或 Prim 算法？那可不行，边数是 $O(N^2)$ 级别的，对于 $N=10^5$ 来说太慢了，会超时的说！

这里就需要一个更聪明的办法了，它通常和01-Trie树以及分治思想有关。

想象一下，我们把所有的势值 $d_i$ 的二进制表示都插入到一棵01-Trie树里。Trie树的每一层对应一个二进制位。

我们的目标是连接所有这些数值点，使得总代价最小。我们可以采用分治的思想来解决这个问题：

考虑当前所有数值的最高有效位（比如从第30位开始）。这些数可以被分成两组：最高位是0的一组，和最高位是1的一组。
为了将整个图连通，我们至少需要一条边来连接“0组”和“1组”。我们当然要选那条连接两个组的、权值最小的边。这条边的权值是多少呢？它就是 $\min_{x \in \text{0-组}, y \in \text{1-组}} (x \oplus y)$ 。
加上这条连接边后，我们还需要确保“0组”内部是连通的，“1组”内部也是连通的。这不就是两个规模更小的子问题了嘛！我们可以递归地去解决它们。

所以，总的最小生成树权值 = (连接0组和1组的最小代价) + (0组内部的MST代价) + (1组内部的MST代价)。

这个递归过程完美地对应了Trie树的结构：

一个Trie节点代表了一组数。
如果一个节点同时有左孩子（代表下一位是0）和右孩子（代表下一位是1），这就对应了我们刚才说的分组情况。
我们需要计算连接左子树代表的数集和右子树代表的数集的最小代价边。
然后递归地对左、右子树计算它们内部的MST代价。

如何计算两个数集之间的最小异或和？ 这也是一个经典Trie应用！要计算 min_xor(SetA, SetB)，我们可以遍历 SetA 中的每个数，在 SetB 对应的Trie树中查询与它异或值最小的数。但这样还是慢。一个更高效的方法是同时在两个集合对应的Trie子树上进行递归搜索。假设我们正在比较A的子树 nodeA 和B的子树 nodeB，在第 k 位：

为了让异或值小，我们优先匹配相同的位。如果 nodeA 的0孩子和 nodeB 的0孩子都存在，我们就递归到 (nodeA->c[0], nodeB->c[0])。同理，也考虑 (nodeA->c[1], nodeB->c[1])。
如果无法匹配相同的位（比如 nodeA 只有0孩子，nodeB 只有1孩子），那我们别无选择，只能交叉匹配。这一位上异或的结果必定是1，贡献了 $2^k$ 的代价，然后我们再递归到更低的位去最小化剩余部分的代价。

通过这个方法，我们就可以高效地解决XOR-MST问题啦！

代码实现

这是本喵根据上面的思路，精心为你准备的一份代码~ 注释很详细的哦，希望能帮到你！

cpp

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

using namespace std;

const int MAXN = 100005;
const int BITS = 30; // 权值最大约为 10^9，需要约30位

// --- 图的基本结构和势的计算 ---
vector<pair<int, int>> adj[MAXN];
long long potential[MAXN];
bool visited[MAXN];

// DFS计算每个节点的势
void dfs_calculate_potential(int u, long long current_potential) {
    visited[u] = true;
    potential[u] = current_potential;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int weight = edge.second;
        if (!visited[v]) {
            dfs_calculate_potential(v, current_potential ^ weight);
        }
    }
}

// --- 01-Trie树及XOR-MST求解 ---
struct TrieNode {
    int children[2];
    TrieNode() {
        children[0] = children[1] = 0;
    }
};

vector<TrieNode> trie;
int trie_nodes_count;

void init_trie() {
    trie.assign(2, TrieNode()); // 节点0是哨兵，节点1是根
    trie_nodes_count = 1;
}

void insert_trie(long long val) {
    int current_node = 1;
    for (int i = BITS - 1; i >= 0; --i) {
        int bit = (val >> i) & 1;
        if (trie[current_node].children[bit] == 0) {
            trie[current_node].children[bit] = ++trie_nodes_count;
            trie.emplace_back();
        }
        current_node = trie[current_node].children[bit];
    }
}

// 寻找连接两组数的最小代价边
long long find_min_connection_cost(int u_node, int v_node, int bit_level) {
    if (bit_level < 0) {
        return 0;
    }
    long long min_cost = -1; // 用-1表示无穷大

    // 尝试匹配 0-0
    if (trie[u_node].children[0] && trie[v_node].children[0]) {
        long long cost = find_min_connection_cost(trie[u_node].children[0], trie[v_node].children[0], bit_level - 1);
        if (min_cost == -1 || cost < min_cost) {
            min_cost = cost;
        }
    }
    // 尝试匹配 1-1
    if (trie[u_node].children[1] && trie[v_node].children[1]) {
        long long cost = find_min_connection_cost(trie[u_node].children[1], trie[v_node].children[1], bit_level - 1);
        if (min_cost == -1 || cost < min_cost) {
            min_cost = cost;
        }
    }

    // 如果可以同位匹配，就已经找到了最小路径，因为高位是0
    if (min_cost != -1) {
        return min_cost;
    }

    // 只能交叉匹配了，比如 0-1
    long long cost1 = -1;
    if (trie[u_node].children[0] && trie[v_node].children[1]) {
        cost1 = find_min_connection_cost(trie[u_node].children[0], trie[v_node].children[1], bit_level - 1);
    }
    // 或者 1-0
    long long cost2 = -1;
    if (trie[u_node].children[1] && trie[v_node].children[0]) {
        cost2 = find_min_connection_cost(trie[u_node].children[1], trie[v_node].children[0], bit_level - 1);
    }
    
    // 从两种交叉匹配中选一个代价小的
    if (cost1 != -1 && (cost2 == -1 || cost1 < cost2)) {
        min_cost = cost1;
    } else {
        min_cost = cost2;
    }

    // 加上当前位的代价 (1LL << bit_level)
    return min_cost + (1LL << bit_level);
}

// 递归计算MST的总代价
long long calculate_mst_cost(int u_node, int bit_level) {
    if (u_node == 0 || bit_level < 0) {
        return 0;
    }
    
    int left_child = trie[u_node].children[0];
    int right_child = trie[u_node].children[1];

    // 如果只有一个分支，说明这个位上所有数都一样，直接递归到下一位
    if (left_child == 0) {
        return calculate_mst_cost(right_child, bit_level - 1);
    }
    if (right_child == 0) {
        return calculate_mst_cost(left_child, bit_level - 1);
    }

    // 如果两个分支都存在，需要连接它们，并递归处理各自内部
    long long connection_cost = find_min_connection_cost(left_child, right_child, bit_level - 1) + (1LL << bit_level);
    long long left_mst_cost = calculate_mst_cost(left_child, bit_level - 1);
    long long right_mst_cost = calculate_mst_cost(right_child, bit_level - 1);
    
    return connection_cost + left_mst_cost + right_mst_cost;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 题目给的是0-indexed, 我们内部用1-indexed处理
        adj[u + 1].push_back({v + 1, w});
        adj[v + 1].push_back({u + 1, w});
    }

    // 1. 计算所有顶点的势
    fill(visited + 1, visited + n + 1, false);
    dfs_calculate_potential(1, 0);

    // 2. 将所有势插入Trie树
    init_trie();
    trie.reserve(n * (BITS + 1)); // 预分配内存，加速
    for (int i = 1; i <= n; ++i) {
        insert_trie(potential[i]);
    }

    // 3. 在Trie树上使用分治法计算MST总权值
    long long total_min_cost = calculate_mst_cost(1, BITS - 1);

    cout << total_min_cost << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \log W)$
- 计算所有顶点的势值需要一次DFS，复杂度为 $O(N)$ 。
- 将 $N$ 个势值插入到01-Trie树中，每个数值的插入深度为 $\log W$ （ $W$ 是权值的最大值），所以这部分是 $O(N \log W)$ 。
- 在Trie树上递归计算MST代价，calculate_mst_cost 和 find_min_connection_cost 函数会遍历Trie树的每个节点常数次。Trie树的节点总数最多为 $O(N \log W)$ 。因此，求解MST的复杂度也是 $O(N \log W)$ 。
- 综上，总时间复杂度为 $O(N \log W)$ ，非常高效的说！
空间复杂度: $O(N \log W)$
- 存储图的邻接表需要 $O(N)$ 的空间。
- 存储势值的数组需要 $O(N)$ 的空间。
- 01-Trie树是空间占用的主要部分，它最多有 $O(N \log W)$ 个节点。
- 所以，总空间复杂度为 $O(N \log W)$ 。

知识点总结

这道题真是一次奇妙的冒险，喵~ 我们来总结一下途中的宝藏吧：

图论中的势能分析: "环路异或和为0" 这个性质可以转化为 "任意两点间路径异或和唯一"，从而引出“势”的概念，使得边权 $w_{uv}$ 可以表示为 $p_u \oplus p_v$ 。这是一个非常重要的思想转换！
最小生成树 (MST): 当问题要求在满足一定代价规则下连接所有点且总代价最小时，要立刻想到MST！
XOR-MST 问题: 在完全图上，若边权为顶点权值的异或，求MST是一个特殊问题。直接用暴力算法会超时。
01-Trie树与分治: 解决XOR相关问题的神器！通过按位分组，将问题分解为更小的子问题。Trie树的结构天然地支持了这种分治策略。

希望本喵的讲解能对你有所帮助，让你在算法的道路上越走越远，喵~ 加油哦！

Graph - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键条件：环的异或和为 0 ​

问题的转化 ​

高效求解 XOR-MST ​

代码实现 ​

复杂度分析 ​

知识点总结 ​