C. Canal Crossing 解题思路

核心问题分析

题目的背景非常有画面感：在威尼斯旅游，有 $n$ 个地点。地点之间由“街道”和“桥梁”连接。我们要规划一条旅游路线，要求：

从任意地点出发，最后回到起点（形成闭合回路）。
每座桥梁必须恰好走过一次（权值为 0）。
每条街道最多走过一次（有各自的长度权值 $w$ ）。
使得走过的街道总长度最短。

题目还给了一个极其重要的隐藏条件：“仅通过街道，有且仅有一种方法到达任何其他地方”。这句话在算法竞赛里就是明示：所有的街道构成了一棵树！

1. 破题关键：欧拉回路与“一笔画”

既然要求走一个闭合回路，并且有些边必须走，有些边最多走一次，这不可避免地让人联想到图论中经典的欧拉回路（一笔画问题）。

欧拉回路存在的最核心条件是什么？——图中所有节点的度数（连边的数量）必须是偶数！ 因为你只要“进入”一个节点，就必须“离开”这个节点。进出成对，度数必然为偶数。

在这道题中，桥是必须走的。如果我们单独把所有的桥画出来，有些节点连接的桥的数量是奇数，有些是偶数。为了让所有节点最终的度数都变成偶数，我们必须从“街道（树）”中挑选一部分边加进来，来修补那些度数为奇数的节点！

2. 树上的奇偶性传递：自底向上，唯一解！

明确了我们的任务是“挑街道修补奇偶性”后，问题迎刃而解。因为街道是一棵树，树有一个非常美妙的性质：任意两个节点之间的路径是唯一的。

想象一下树的最底层的叶子节点。

如果这个叶子节点连接的桥的数量是奇数：它必须再连一条边才能凑成偶数！而它在树上只有一条边连向它的父节点。所以，它通向父节点的那条街道，必须被选中！
如果这个叶子节点连接的桥的数量是偶数：它已经完美了。由于每条街道最多用一次，如果它选了通向父节点的街道，它的度数又变成奇数了。所以，它通向父节点的街道，绝对不能被选中！

顿悟时刻： 每一个节点的奇偶性修补，只能依靠它与父节点之间的那条边。如果它当前度数是奇数，就必须选上这条边，选中后，它自己的奇偶性变偶了，但它父节点的奇偶性会被翻转（因为父节点也连了这条边）。如果度数是偶数，就不选。

因此，我们只需要**自底向上（从叶子到根）**扫描整棵树，遇到奇数节点就“强行”选上连向父亲的边，并把父节点的奇偶性翻转。最后累加选中的边的权值，就是最短的旅行长度！

3. 代码实现技巧：BFS 替代 DFS 递归

很多同学遇到“自底向上”会本能地写 DFS（深度优先搜索）递归，但在数据量较大时（本题 $n \le 10^5$ ），递归容易爆栈或者常数较大。

这套代码里使用了一个极其优雅的非递归写法：

先用 BFS（广度优先搜索） 跑出一遍树的拓扑层级遍历序（存入 order 数组），同时记录每个节点的父节点 p[v] 和边权 weight[v]。
将 order 数组逆序遍历（从 $n-1$ 倒着遍历到 $1$ ），这天然就是一个完美的自底向上处理过程！

CPP 代码实现

cpp

// C. Canal Crossing

#include <bits/stdc++.h>
#define lg(x) (63 - __builtin_clzll(x))
#define all(x) (x).begin(), (x).end()
#define low_bit(x) ((x) & (-x))
#define pb push_back
#define db long double
#define int long long
#define endl "\n"

using namespace std;

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

    // adj 存储由“街道”构成的树，包含相连节点和边权
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }

    int m;
    cin >> m;
    
    // temp 数组就是我们的“奇偶性标记器”
    // temp[u] = 1 表示节点 u 目前连接的必经之边(桥+已确定的街道)数量为奇数
    // temp[u] = 0 表示偶数
    vector<int> temp(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // 每连一条桥，两个端点的奇偶性就翻转一次
        temp[u] ^= 1;
        temp[v] ^= 1;
    }

    vector<int> order;            // 记录 BFS 的遍历顺序（从根到叶子）
    vector<int> p(n + 1, 0);      // 记录每个节点的父节点
    vector<int> weight(n + 1, 0); // 记录每个节点连向父节点的街道长度
    vector<bool> vis(n + 1, false);

    // 假设 1 号节点为根，启动 BFS
    order.pb(1);
    vis[1] = true;

    int head = 0;
    while (head < order.size()) {
        int u = order[head++];
        for (auto edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (!vis[v]) {
                vis[v] = true;
                p[v] = u;         // 记录父节点
                weight[v] = w;    // 记录到父节点的边权
                order.pb(v);      // 加入队列
            }
        }
    }

    int ans = 0;

    // 核心逻辑：自底向上修补奇偶性
    // 逆序遍历 BFS 得到的 order 数组，正好就是从最底层的叶子节点一层层往上剥
    for (int i = n - 1; i >= 1; --i) {
        int u = order[i];
        
        // 如果当前节点 u 的度数是奇数，必须通过连向父亲的边来凑偶数
        if (temp[u]) {
            ans += weight[u];     // 选中这条边，加上权值
            temp[p[u]] ^= 1;      // 这条边也连着父节点，导致父节点的奇偶性被翻转
        }
    }
    
    // 由于题目保证必定有解，最终到达根节点 1 时，它的奇偶性必然已经被子节点们修补为偶数了
    cout << ans << endl;
}

signed main() {
    // 优化输入输出，竞技编程好习惯
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t; // 本题仅一组数据

    while (t--) {
        solve();
    }
}

C. Canal Crossing 解题思路 ​

核心问题分析 ​

1. 破题关键：欧拉回路与“一笔画” ​

2. 树上的奇偶性传递：自底向上，唯一解！ ​

3. 代码实现技巧：BFS 替代 DFS 递归 ​

CPP 代码实现 ​