给你 个点, 条白边, 条黑边,问删去 条白边, 条黑边可以把树恰好分为两部分的方案数
对每条白边来说:(删这个白边)
1.这个白边属于一个环,那么删掉构成环的黑边:种方案;
2.这个白边属于多个环,那么删一条黑边无用: 种方案
3.这个白边不在环上,那么可以删除任意一条黑边, 种方案。
怎么判断环:每条黑边 求 , 那么利用树上的差分 代表这个点上方的边所在环的数目。
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N = 2e5 + 5; inline int read(){ int x = 0;char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } struct edge{int to,next;}e[N<<1]; int head[N],tot; inline void add(int u,int v){ e[++tot] = (edge){v,head[u]}; head[u] = tot; } int dep[N],siz[N],fa[N],son[N]; long long ans; void dfs1(int x,int ff){ dep[x] = dep[ff] + 1; siz[x] = 1; fa[x] = ff; for(int i = head[x];i;i = e[i].next){ int v = e[i].to; if(v == ff) continue; dfs1(v,x); siz[x] += siz[v]; if(siz[son[x]] < siz[v]) son[x] = v; } } int top[N],cha[N],n,m; void dfs2(int x,int tp){ top[x] = tp; if(son[x]) dfs2(son[x],tp); for(int i = head[x];i;i = e[i].next){ int v = e[i].to; if(v == fa[x] || v == son[x]) continue; dfs2(v,v); } } inline int lca(int x,int y){ while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x,y); x = fa[top[x]]; } return dep[x] < dep[y] ? x : y; } void dfs3(int x){ for(int i = head[x];i;i = e[i].next){ int v = e[i].to; if(v == fa[x]) continue; dfs3(v); cha[x] += cha[v]; } if(x > 1){ if(!cha[x]) ans += m;//不属于任何环 else if(cha[x] == 1) ++ans;//属于1个环 } } int main(){ n = read(); m = read();int u,v; for(int i = 1;i < n;++i){ u = read(); v = read(); add(u,v); add(v,u); } dfs1(1,0); dfs2(1,1); for(int i = 1;i <= m;++i){ u = read(); v = read(); ++cha[u]; ++cha[v]; cha[lca(u,v)] -= 2; } dfs3(1); printf("%lld",ans); }