悬2关
by Just_A_Sentence @ 2024-04-23 19:16:03
```cpp
#include<bits/stdc++.h>
using namespace std;
struct tree{
int num;
int to,nxt;
}tr[100005];
int head[100005],LCA[100005][20],cnt=0,dep[100005],ans=0,n,m;
void add(int u,int v){
tr[++cnt].to=v;
tr[cnt].nxt=head[u];
head[u]=cnt;
}
void lca(int x,int fa){
LCA[x][0]=fa;
dep[x]=dep[fa]+1;
for(int i=1;i<=19;i++) LCA[x][i]=LCA[LCA[x][i-1]][i-1];
for(int i=head[x];i;i=tr[i].nxt){
if(tr[i].to!=fa) lca(tr[i].to,x);
}
}
void dfs(int x,int y){
tr[x].num++;
tr[y].num++;
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--){
if(dep[LCA[x][i]]>=dep[y]) x=LCA[x][i];
}
if(x==y){
tr[x].num-=2;
return;
}
for(int i=19;i>=0;i--){
if(LCA[x][i]!=LCA[y][i]){
x=LCA[x][i];
y=LCA[y][i];
}
}
tr[LCA[x][0]].num-=2;
}
void find(int x,int fa){
if(tr[x].to==0){
if(tr[x].num==0) ans+=m;
if(tr[x].num==1) ans++;
return;
}
for(int i=head[x];i;i=tr[i].nxt){
if(tr[i].to!=fa){
find(tr[i].to,x);
tr[x].num+=tr[tr[i].to].num;
}
}
if(tr[x].num==0&&x!=1) ans+=m;
if(tr[x].num==1&&x!=1) ans++;
return;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
lca(1,0);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
dfs(x,y);
}
find(1,0);
printf("%d",ans);
return 0;
}
```
$40$分
by Just_A_Sentence @ 2024-04-23 19:16:35
建议你发学术区（大能较多）
by WA_and_AC @ 2024-04-23 19:30:09
@[xuhengyi1](/user/502314) 简单说一下思路，不明白为什么要用LCA
by I_AK_CSP_J @ 2024-04-23 19:32:29
@[I_AK_CSP_J](/user/1080722)
显然主要边构成了一棵树，所以把一条附加边$(x,y)$添加到主要边所构成的树中，会与树上$x,y$之间的路径一起形成一个环。如果第一步切断$x,y$之间路径上的某条边，那么第二步就必须切断附加边$(x,y)$。
因此，我们称每条附加边$(x,y)$都把树上$x,y$之间路径上的每条边“覆盖了一次”，我们只需要用树上差分统计每条主要边被覆盖了几次，令节点$x,y$权值加$1$，节点$LCA(x,y)$权值减$2$，最后$DFS$求以$x$为根的子树的权值之和$F[x]$，$F[x]$就表示$x$和它的父节点之间的边被覆盖了几次，若第一步切断的主要边被覆盖了$0$次，则第二步可切断任意一条附加边，若第一步切断的主要边被覆盖了$1$次，则第二步方法唯一，若第一步切断的主要边被覆盖了超过$2$次，则第二步无论如何都不能击败Dark。
by Just_A_Sentence @ 2024-04-23 19:58:41
楼主ACed此题，此帖结。~~数组开小RE了~~
by Just_A_Sentence @ 2024-05-13 23:07:46