使用C++实验用LCA+路径压缩的方式求桥

LCA+路径压缩的方式可以用于求解树上的桥，具体实现步骤如下：

1. 对于树上每个节点，记录其在树中的深度（或者高度）以及其父亲节点。
2. 对于每个节点，记录其在树上的最小深度（或最小高度）以及其所在子树中深度最小的节点。
3. 对于每条边(u, v)，设u的深度小于v的深度（或者高度），则如果v的子树中没有深度小于u的节点，则(u, v)是桥。

具体的实现过程如下：

首先，我们需要对树进行预处理，求出每个节点的深度以及其父亲节点。可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。在这里我们使用DFS来实现：

vector<int> adj[MAX_N]; // 树的邻接表
int n; // 树的节点数
int dep[MAX_N], fa[MAX_N]; // dep[i]表示节点i的深度，fa[i]表示节点i的父亲节点

void dfs(int u, int f, int d) {
    dep[u] = d;
    fa[u] = f;
    for (int v : adj[u]) {
        if (v != f) {
            dfs(v, u, d + 1);
        }
    }
}

接下来，我们需要计算每个节点所在子树中深度最小的节点。我们可以使用LCA（最近公共祖先）的方法来实现。具体来说，我们可以使用倍增算法来预处理出每个节点的2^k级祖先，并且在查询LCA时使用路径压缩的方式优化时间复杂度。这里我们不展开讲解LCA和倍增算法的细节，如果你对此感兴趣，可以参考其他资料进行学习。

const int MAX_LOG_N = 20; // log2(n)的上取整

int anc[MAX_N][MAX_LOG_N]; // anc[i][j]表示节点i的2^j级祖先
int mn[MAX_N]; // mn[i]表示节点i所在子树中深度最小的节点

void precompute() {
    // 预处理anc数组
    for (int j = 1; j < MAX_LOG_N; j++) {
        for (int i = 1; i <= n; i++) {
            if (anc[i][j - 1] != -1) {
                anc[i][j] = anc[anc[i][j - 1]][j - 1];
            }
        }
    }

    // 计算mn数组
    for (int i = 1; i <= n; i++) {
        mn[i] = i;
        for (int j = 0; (1 << j) <= dep[i]; j++) {
            if ((dep[i] & (1 << j)) != 0) {
                mn[i] = min(mn[i], mn[anc[i][j]]);
                i = anc[i][j];
            }
        }
    }
}

最后，我们可以使用LCA+路径压缩的方式来判断每条边是否为桥。具体来说，对于每条边(u, v)，我们需要判断v的子树中是否存在深度小于u的节点。如果存在，则(u, v)不是桥，否则(u, v)是桥。

bool is_bridge(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    if (mn[v] != u) return true; // 子树中存在深度小于u的节点
    return false; // 子树中不存在深度小于u的节点
}

完整代码如下：