【题解】 闇の連鎖
题目链接
解题思路
请见李煜东的蓝书,里面的讲解比任何博客都好。
说白了就是一个 “覆盖”,然后用树上查分 O(1) 维护树上边被覆盖的次数,以点代边,边所连的子节点作为这条边的“配套点”。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int head[100005];
struct e{
int nxt,to;
}edge[200005];
int tot=0;
void add_edge(int u,int v){
tot++;
edge[tot].nxt=head[u];
edge[tot].to=v;
head[u]=tot;
}
int father[30][100005];
int depth[100005];
int logg;
int num[100005];
void DFS(int now,int f,int d){
father[0][now]=f;
depth[now]=d;
for(int i=head[now];i;i=edge[i].nxt){
if(edge[i].to!=f){
DFS(edge[i].to,now,d+1);
}
}
}
void init(){
DFS(1,-1,1);
for(int i=1;i<=logg;i++){
for(int j=1;j<=n;j++){
father[i][j]=father[i-1][father[i-1][j]];
}
}
}
int LCA(int a,int b){
if(depth[a]<depth[b])swap(a,b);//a深度比b大
for(int i=logg;i>=0;i--){
if(depth[father[i][a]]>=depth[b]){
a=father[i][a];
}
}
if(a==b){
return a;
}
for(int i=logg;i>=0;i--){
if(father[i][a]!=father[i][b]){
a=father[i][a],b=father[i][b];
}
}
return father[0][a];
}
int sum[100005];
int dfs(int now,int f){
sum[now]=0;
int cnt=0;
for(int i=head[now];i;i=edge[i].nxt){
cnt++;
if(edge[i].to!=f){
sum[now]+=dfs(edge[i].to,now);
}
}
sum[now]+=num[now];
return sum[now];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
sum[i]=-1;
}
logg=log2(n)+1;
int u,v;
for(int i=1;i<=n-1;i++){
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
init();
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
num[u]++;
num[v]++;
num[LCA(u,v)]-=2;
}
int tmp=dfs(1,-1);
sum[1]=-1;
int ans=0;
for(int i=1;i<=n;i++){
if(sum[i]==0){
ans+=m;
}else if(sum[i]==1){
ans+=1;
}
}
printf("%d",ans);
return 0;
}