- 题目链接：「一本通 4.4 例 2」暗的连锁
- 题目标签：LCA，（树上差分）
- 题目大意：请自行读题。。。
题目分析：对于一条附加边[x,y]，如果将原树分开后x,y分成了两个部分，那么下一步就必须把x,y切开。通过研究样例，我们不妨这样想，对于每一条附加边[x,y]，我们就说 _从x到y的路径上的节点被覆盖了一次_ ，那么对于每个节点，无疑有三种情况：
- 1.该节点到根节点没有被覆盖过，那么下一步可以随意切一条边，故有M种方案。
- 2.该节点到根节点被覆盖过1次，那么下一步只能切除被分开的x,y。
3.该节点到根节点被覆盖过>=2次，那么下一步无论怎样切割都无法达到要求。
那我们就把问题简化成了：对于每一条附加边，把它们的路径上的节点覆盖一次，然后枚举除了根节点之外的节点，累加方案数。
- 关于优化：如果暴力覆盖的话肯定会TLE，那我们就来差分一下，也就是树上差分，在这里不做详细解释，搬来一篇解释差分的洛谷日报，不会的读者请自行学习。。。
- 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
using namespace std;
int sc() {
int xx=0,ff=1; char cch;
while(cch<'0'|| cch>'9') {
if(cch=='-') ff=-ff; cch=gc;
}
while(cch>='0'&& cch<='9') {
xx=xx*10+(cch-48); cch=gc;
}
return xx*ff;
}
struct EDGE {
int next,to;
}edge[Maxn*2];
int n,m,ans,cnt;
int head[Maxn*2],deep[Maxn],w[Maxn],ww[Maxn];
int f[Maxn][21];
namespace DY {
void ADD(int from,int to) {
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
void D_F(int son,int fa) { //LCA的板子(From line30 to line52)
deep[son]=deep[fa]+1;
for(int i=0; i<=19; i++)
f[son][i+1]=f[f[son][i]][i];
for(int i=head[son]; i; i=edge[i].next) {
int to=edge[i].to;
if(to==fa) continue;
f[to][0]=son;
D_F(to,son);
}
}
int LCA(int x,int y) {
if(deep[x]<deep[y]) swap(x,y);
for(int i=20; i>=0; i--) {
if(deep[f[x][i]]>=deep[y]) x=f[x][i];
if(x==y) return x;
}
for(int i=20; i>=0; i--) {
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
return f[x][0];
}
void dfs(int son,int fa) { //遍历赋值
for(int i=head[son]; i; i=edge[i].next) {
int to=edge[i].to;
if(to==fa) continue;
dfs(to,son);
ww[son]+=ww[to];
}
}
void main() {
n=sc(); m=sc();
for(int i=1; i<n; i++) {
int u=sc(),v=sc();
ADD(u,v); ADD(v,u);
}
deep[1]=1;
D_F(1,0);
for(int i=1; i<=m; i++) { //树上差分
int u=sc(),v=sc();
w[u]++; w[v]++;
w[LCA(u,v)]-=2;
}
for(int i=1; i<=n; i++) //ww[i]为第i个节点到根节点被覆盖的次数
ww[i]=w[i];
dfs(1,0); //进行遍历来赋值
for(int i=2; i<=n; i++) {
if(!ww[i]) ans+=m;
else if(ww[i]==1) ans+=1;
}
printf("%d",ans);
}
};
int main() {
DY::main();
return 0;
}