一、题目描述

给定一棵由 $n$ 个节点组成的树和 $m$ 个无序数对 $(a_i,b_i)$，要求找到一条边，使得砍断这条边后，所有数对中的两个节点都不连通。若存在多条满足条件的边，输出编号最大的；否则输出 -1。

二、题目分析

暴力实现思路

1. 枚举每条边：尝试删除每条边，检查是否满足所有数对不连通
2. 连通性检查：对每个数对使用DFS/BFS检查连通性
3. 时间复杂度：$O(m\times n^2)$，只能通过30%数据

正解思路

1. 关键观察：满足条件的边必须被所有数对的路径覆盖
2. 高效统计：使用树上差分快速统计每条边被路径覆盖的次数
3. 算法选择：LCA（最近公共祖先）+ 树上差分

三、解题思路 + 算法介绍

1. LCA预处理

• 倍增法预处理每个节点的 $2^k$ 级祖先
• 支持 $O(\log n)$ 时间查询任意两节点的LCA

2. 树上差分

• 边差分：将边权下放到子节点
• 对每个数对 $(a_i,b_i)$：
  • diff[a_i]++, diff[b_i]++（路径端点标记）
  • diff[lca(a_i, b_i)] -= 2（消除LCA以上影响）

3. 统计覆盖次数

• DFS后序遍历累加差分值
• diff[v] 表示边 $u\to v$ 被覆盖的次数

四、代码实现

暴力代码（30分）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> path;
int w[N], h[N], e[N<<1], ne[N<<1], idx;

void add(int a, int b) { e[idx]=b, ne[idx]=h[a], h[a]=idx++; }

bool dfs(int u, int fa, int v) {
    if (u == v) return true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        path.push_back(i/2 + 1);
        if (dfs(j, u, v)) return true;
        path.pop_back();
    }
    return false;
}

int main() {
    memset(h, -1, sizeof h);
    int n, m; cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        add(a, b), add(b, a);
    }
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        path.clear();
        dfs(a, -1, b);
        for (int e : path) w[e]++;
    }
    int ans = -1;
    for (int i = n-1; i >= 1; i--)
        if (w[i] == m) { ans = i; break; }
    cout << ans;
}

正解代码（100分）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, diff[N], depth[N], f[N][20], cnt[N], ans = -1;
int h[N], e[N<<1], ne[N<<1], id[N<<1], idx;

void add(int a, int b, int c) { e[idx]=b, id[idx]=c, ne[idx]=h[a], h[a]=idx++; }

void bfs() {
    memset(depth, 0x3f, sizeof depth);
    queue<int> q; q.push(1); depth[1] = 1;
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (depth[v] > depth[u] + 1) {
                depth[v] = depth[u] + 1;
                f[v][0] = u;
                for (int k = 1; k < 20; k++)
                    f[v][k] = f[f[v][k-1]][k-1];
                q.push(v);
            }
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 19; k >= 0; k--)
        if (depth[f[a][k]] >= depth[b])
            a = f[a][k];
    if (a == b) return a;
    for (int k = 19; k >= 0; k--)
        if (f[a][k] != f[b][k])
            a = f[a][k], b = f[b][k];
    return f[a][0];
}

void dfs(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        dfs(v, u);
        diff[u] += diff[v];
        if (id[i] != -1 && diff[v] == m)
            ans = max(ans, id[i]);
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        add(a, b, i), add(b, a, i);
    }
    bfs();
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        diff[a]++, diff[b]++;
        diff[lca(a, b)] -= 2;
    }
    dfs(1, -1);
    cout << ans;
}

五、重点细节

1. 边编号处理：
   • 无向边存储两次，通过 id[i] 避免重复统计
   • i/2 + 1 将邻接表索引转为边编号
2. 差分还原：
   • DFS后序遍历确保先处理子树
   • diff[v] 直接表示边 $u\to v$ 的覆盖次数
3. LCA优化：
   • 使用BFS初始化避免递归栈溢出
   • 哨兵节点 depth[0] = 0 处理边界

六、复杂度分析

七、总结

1. 暴力法：简单直观但效率低，适用于小数据
2. 正解法：
   • 利用LCA快速定位路径
   • 树上差分高效统计覆盖次数
   • 完美结合树结构的递归特性
3. 关键技巧：边权下放、差分标记、后序统计
4. 适用场景：需要高效处理树上路径覆盖统计的问题