352. 闇の連鎖（树上差分，LCA）

352. 闇の連鎖 - AcWing题库

传说中的暗之连锁被人们称为 Dark。

Dark 是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。

经过研究，你发现 Dark 呈现无向图的结构，图中有 N 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。

Dark 有 N–1 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。

另外，Dark 还有 M 条附加边。

你的任务是把 Dark 斩为不连通的两部分。

一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。

一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。

但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道，一共有多少种方案可以击败 Dark。

注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。

输入格式

第一行包含两个整数 N 和 M。

之后 N–1 行，每行包括两个整数 A 和 B，表示 A 和 B 之间有一条主要边。

之后 M 行以同样的格式给出附加边。

输出格式

输出一个整数表示答案。

数据范围

N≤100000,M≤200000，数据保证答案不超过2^31−1

输入样例：

4 1
1 2
2 3
1 4
3 4

输出样例：

3

解析： 

”主要边“构成一棵树，”附加边“则是”非树边“。把一条附加边（x，y）添加到主要边构成的树中，会与树上 x，y 之间的路径形成一个环。如果第一步选择切断 x，y 之间路径上的某条边，那么第二步就必须切断附加边（x，y），才能令dark被斩为不连通的两部分。

因此，我们称每条附加边（x，y）都把树上 x，y 之间的路径上的每条边“覆盖了一次”。我们只需要统计出每条“主要边”被覆盖了多少次。若第一步把被覆盖0次的主要边切断，则第二步可以任意切断一条附加边。若第一次把覆盖1次的主要边切断，则第二步只能切断一条附加边。若第一次把覆盖2次及2次以上的主要边切断，则第二步怎么且都不能满足题意。据此我们可以统计出所有的方案数。

综上所述，下面我们要解决的问题模型是：给定一张无向图和一棵生成树，求每条“树边”被“非树边”覆盖了多少次。

解决此问题的经典做法就是“树上差分”。我们给树上每个节点一个初始为0的权值，然后对每条非树边（x，y），令节点 x 的权值加1，节点 y 的权值加1，节点 LCA（x，y）的权值减2。最后对这棵生成树进行一次深度优先遍历，求出 F[x] 表示以 x 为根的子树中各节点的权值之和。F[x] 就是 x 与它的父节点之间的“树边”被覆盖的次数。时间复杂度为 O（N+M）。

 

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 2e5 + 5, INF = 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], idx;
int depth[N],fa[N][17],d[N];
int q[N];
int ans;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void bfs() {int hh = 0, tt = 0;memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;q[tt++] = 1;while (hh != tt) {int t = q[hh++];if (hh == N)hh = 0;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q[tt++] = j;if (tt == N)tt = 0;fa[j][0] = t;for (int k = 1; k <= 16; k++) {fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}}
}int lca(int a, int b) {if (depth[a] < depth[b])swap(a, b);for (int k = 16; k >= 0; k--) {if (depth[fa[a][k]] >= depth[b])a = fa[a][k];}if (a == b)return a;for (int k = 16; k >= 0; k--) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];
}int dfs(int u,int father){int ret = d[u];for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (j != father) {int s = dfs(j, u);if (!s)ans += m;else if (s == 1)ans++;ret += s;}}return ret;
}int main() {cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1,a,b,c; i < n; i++) {scanf("%d%d", &a, &b);add(a, b), add(b, a);}bfs();for (int i = 1,a,b; i <= m; i++) {scanf("%d%d", &a, &b);int p = lca(a, b);d[a]++, d[b]++, d[p] -= 2;}dfs(1,-1);cout << ans << endl;return 0;
}