题解：P11712 「KTSC 2020 R2」冰战
devout
·
·
题解
题目描述
有一个图，问是否能删不超过两条边使得它变成一个二分图，如果不可以输出0，否则输出删除边数最少得方案数。
题目解答
发现这个图几乎是一个二分图，所以可以考虑先做一个二分图染色，得到了一棵 dfs 树，这棵树的非树边一定是返祖边。一条非树边可以和树边形成一个环，如果是奇环则称其为奇边，否则称其为偶边，显然如果没有奇边则直接输出 1 即可。
设 S 为所有奇边的集合对每条边 e，若 e 是一条非树边，则 T(e)=\{e\}，否则设 e=(u,fa_u)，定义 T(e) 是所有 u 子树到 u 子树外的返祖边的集合。
若最少删一条边
如果删的是非树边 e，则删的一定是唯一的一条奇边。
如果删的是树边 e=(u,fa_u)，显然 S\subset T(e)，而如果 T(e)\neq S，任取偶边 e_1\in T(u)\setminus S，奇边 e_2\in T(u)\cap S，e_1,e_2 和若干条（偶数条）依然构成一个奇环。
综上，删一条边的情况等价于 \exist e\ s.t. \ T(e)=S。
若最少删两条边
设删去 x_1,x_2 两条边，设 A_i=T(x_i)\cap S,B_i=T(x_i)\setminus S,i=1,2。
显然 A_i,B_i 均非空，否则可以删一条边解决。
任取 e_1\in A_1,e_2\in B_1，e_1,e_2 和树边构成的奇环并没有因为 x_1 切断，因此 x_2 一定切断了这个奇环，这也就意味着对于 x_2 来说，e_2 是跨过这条边的返祖边，即 e_2\in B_2，同时如果 e_1\in A_2，则这个奇环还是没有切断，因此 e_1\not\in A_2，即 B_1\subset B_2,A_1\cap A_2=\emptyset。
对 e_1\in A_2,e_2\in B_2 结论同样成立，因此 B_1=B_2。 又显然任意 e\in S 他至少在 A_1,A_2 之一里，所以可以删两条边的情况等价于：
**程序实现**
发现维护集合是复杂度非常不合理的，可以考虑哈希，注意到我们只需要维护集合，并且需要实现集合的加减等操作，因此可以考虑异或哈希，给每条边随机权值 $h_e$，集合 $S$ 的哈希值 $hash(S)=\oplus_{e\in S}h_e$。
```cpp
mt19937_64 rnd(time(0));
int head[N],ecnt;
int col[N],dep[N];
ull S,T[N];
bool vis[N];
map<ull,int> cnt;
struct Edge{
int to,next;
}e[N<<1];
void add(int x,int y){
e[++ecnt]=(Edge){y,head[x]},head[x]=ecnt;
}
void dfs(int u,int fa){
vis[u]=true;
RepG(i,u){
int v=e[i].to;
if(v==fa)continue;
if(!vis[v]){
col[v]=col[u]^1;
dep[v]=dep[u]+1;
dfs(v,u);
T[u]^=T[v];
}
else if(dep[v]<dep[u]){
ull x=rnd();
T[u]^=x;
T[v]^=x;
if(col[u]==col[v])S^=x;
cnt[x]++;
}
}
cnt[T[u]]++;
}
long long count_ways(int n, std::vector<int> U, std::vector<int> V) {
for(int i=0;i<U.size();i++)add(U[i],V[i]),add(V[i],U[i]);
dfs(1,0);
if(!S)return 1;
else if(cnt[S])return cnt[S];
else{
ll res=0;
for(auto [x,t]:cnt)res+=1ll*t*cnt[x^S];
return res/2;
}
}
```