算法竞赛进阶指南.闇の連鎖

题目

352. 闇の連鎖

算法标签: 树上差分, $LCA$, 倍增

思路

对于一个无向图, 第一次切断树边, 第二次切非树边, 一共多少种方案使得图不连通, 点数和边数都很大, 时间复杂度不能是$O(n^2)$级别的, 对于每一条非树边, 都能计算出删除当前边后, 对于树边还需要删除哪些边, 如何快速的给树上的边加上一个树, 以及快速的求每个边最终的值, 可以使用树上差分

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = N << 1, K = 20;

int n, m;
int head[N], ed[M], ne[M], idx;
int fa[N][K], depth[N];
int w[N], ans;

void add(int u, int v) {
   
    ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u, int pre, int dep) {
   
    depth[u] = dep;
    fa[u][0] = pre;
    for (int k = 1; k < K; ++k) {
   
        fa[u][k] = fa[fa[u][k - 1]][k - 1];
    }
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == pre) continue;
        dfs(v, u, dep + 1);
    }
}

int lca(int u, int v) {
   
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = K - 1; k >= 0; --k) {
   
        if (depth[fa[u][k]] >= depth[v]) {
   
            u = fa[u][k];
        }
    }
    if (u == v) return u;
    for (int k = K - 1; k >= 0; --k) {
   
        if (fa[u][k] != fa[v][k]) {
   
            u = fa[u][k];
            v = fa[v][k];
        }
    }
    return fa[u][0];
}

int calc(int u, int pre) {
   
    int tmp = w[u];
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == pre) continue;
        
        int val = calc(v, u);
        if (val == 0) ans += m;
        else if (val == 1) ans += 1;
        tmp += val;
    }
    return tmp;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);
    cin >> n >> m;
    for (int i = 0; i < n - 1; ++i) {
   
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }

    dfs(1, -1, 1);

    for (int i = 0; i < m; ++i) {
   
        int u, v;
        cin >> u >> v;
        int f = lca(u, v);
        w[u]++, w[v]++;
        w[f] -= 2;
    }

    calc(1, -1);
    cout << ans << endl;

    return 0;
}