洛谷P10931 闇の連鎖
题意
给定一棵 \(n\) 个点的树，有 \(m\) 条附加边。
第一次删除一条树边，第二次删除一条附加边。
求有多少种方案使原来的树不联通。
思路
考虑求出 \(f_i\) 表示 \(i\) 的子树中有多少条附加边连向 \(i\) 的子树外。
若 \(f_i=0\)，则把 \(i\) 与 \(i\) 的父亲之间的树边删除后树已经不联通，随意删除一条附加边即可，对答案的贡献是 \(m\)。
若 \(f_i=1\)，则把 \(i\) 与 \(i\) 的父亲之间的树边删除后，必须删除这条附加边才能满足题意，对答案的贡献是 \(1\)。
若 \(f_i \ge 2\)，则把 \(i\) 与 \(i\) 的父亲之间的树边删除后，无论删除哪条附加边都不能满足题意，对答案的贡献是 \(0\)。
现在想想如何求出 \(f_i\)。
对于每条附加边 \((u,v)\)，\(u\) 和 \(v\) 对哪些点的 \(f\) 有贡献呢？
从 \(u\) 到 \(LCA(u,v)\)（不含）的路径上，从 \(v\) 到 \(LCA(u,v)\)（不含）的路径上的所有点的 \(f\) 都会加一。
为什么 \(LCA(u,v)\) 以上的点不会有贡献呢？
对于 \(LCA(u,v)\) 及其以上的点 \(x\)，\(u\) 和 \(v\) 都在 \(x\) 的子树中，不满足 \(f\) 的定义，即连向子树外的附加边，所以没有贡献。
那怎么快速计算贡献呢？
暴力更改 \(f\) 时间复杂度为 \(O(nm)\)，不能通过。
树上路径问题可以想到使用树链剖分，不过太复杂。
可以使用树上差分快速统计。
\(u\) 到 \(LCA(u,v)\) 路径上点权全部加一，等价于 \(u\) 到根节点路径上点权全部加一，\(LCA(u,v)\) 到根节点路径上点权全部减一。
可以把 \(f_u\) 加一，\(f_{LCA(u,v)}\) 减一，最后统计答案时遍历一遍把子树内的信息收上来。\(v\) 同理。
时间复杂度 \(O((n+m)\log n)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int tot, ver[N << 1], nxt[N << 1], head[N];
int fa[N][22], de[N];
int n, m, a[N], ans;
void add(int x, int y) {
ver[++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void DFS(int x) {
de[x] = de[fa[x][0]] + 1;
for (int i = 1; i <= 19; i ++)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (int i = head[x], y; i; i = nxt[i]) {
y = ver[i];
if (y == fa[x][0]) continue;
fa[y][0] = x;
DFS(y);
}
}
inline int LCA(int x, int y) {
if (de[x] < de[y]) swap(x, y);
for (int i = 19; i >= 0; i --)
if (de[fa[x][i]] >= de[y]) x = fa[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; i --)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
void dfs(int x, int fa) {
for (int i = head[x], y; i; i = nxt[i]) {
y = ver[i];
if (y == fa) continue;
dfs(y, x);
a[x] += a[y]; // 把子树信息收上来
}
}
signed main() {
cin >> n >> m;
for (int i = 1, x, y; i < n; i ++) {
cin >> x >> y;
add(x, y); add(y, x);
}
DFS(1);
for (int i = 1, x, y; i <= m; i ++) {
cin >> x >> y;
a[x] ++, a[y] ++, a[LCA(x, y)] -= 2; // 差分
}
dfs(1, 0); // 收集信息
for (int i = 2; i <= n; i ++) { // 统计答案
if (!a[i]) {
ans += m;
} else if (a[i] == 1) {
ans ++;
}
}
cout << ans << "\n";
return 0;
}