题解：P10931 闇の連鎖
_1nsect
·
·
题解
树上差分
不会树上差分的看这里。
本题需要解决的是每条“树边”被“非树边”覆盖了多少次，可以使用树上差分的边差分解决。
树的初始状态为 $0$，如果路径 $(x,y)$ 上被“非树边”覆盖一次，则进行一次边差分，$x$ 的点权 $+1$，$y$ 的点权 $+1$，$\operatorname{lca}(x,y)$ 的点权 $-2$ (边差分)。
设连接两点间的“非树边”个数为 $a$，因为可以切断一条“树边”和一条“非树边”，当 $a=0$ 时直接断掉这条“树边”，然后随便断掉一条“非树边”即可；当 $a=1$ 时断掉这条“树边”，只有把这条“非树边”断掉才满足题；当 $a>1$ 时无论断掉那条“树边”，没有方案满足题目。
综上所述：
$a=0$ 时，方案数 $+m$；
$a=1$ 时，方案数 $+1$；
$a>1$ 时，无解，方案数不变。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 10;
int head[maxn], cnt;
int quan[maxn];
int ans = 0;
struct node{
int to;
int nxt;
}e[maxn];
void add(int u, int v){
e[++cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int n, m;
int fa[maxn][30];
int de[maxn];
void dfs(int u, int f){
de[u] = de[f] + 1;
fa[u][0] = f;
for(int i = 1 ; i <= 20 ; i++){
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for(int i = head[u] ; i ; i = e[i].nxt){
int v = e[i].to;
if(v == f){
continue;
}
dfs(v, u);
}
}
int lca(int u, int v){
if(de[u] < de[v]){
swap(u, v);
}
for(int i = 20 ; i >= 0 ; i--){
if(de[fa[u][i]] >= de[v]){
u = fa[u][i];
}
}
if(u == v){
return v;
}
for(int i = 27 ; i >= 0 ; i--){
if(fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
void solve(int u, int f){
for(int i = head[u] ; i ; i = e[i].nxt){
int v = e[i].to;
if(v == f){
continue;
}
solve(v, u);
quan[u] += quan[v];
}
if(u == 1){
return;
}
if(quan[u] == 1){
ans++;
}
if(quan[u] == 0){
ans += m;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> m;
for(int i = 1 ; i < n ; i++){
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1, 0);
for(int i = 1 ; i <= m ; i++){
int a, b;
cin >> a >> b;
int LCA = lca(a, b);
quan[a]++;
quan[b]++;
quan[LCA] -= 2;
}
solve(1, 0);
cout << ans << endl;
return 0;
}
```