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

题目

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;
}