[JOISC2014]電圧
题目大意：
一个\(n(n\le10^5)\)个点，\(m(m\le2\times10^5)\)条边的无向图。要在图中找到一条边，满足去掉这条边后，剩下的图是一个二分图，且若再将这条边接上，两端一定在二分图的同一侧。问有多少这样的边。
思路：
这样的边一定满足在所有奇环的交上，并且不属于任何一个偶环。
随便求出原图的一棵生成树，枚举每一个非树边，若构成奇环，则将对应环上边权+1，否则-1。最后统计边权=奇环个数的边的数量。树链剖分+线段树维护即可。
对于包含多条非树边的环，一定能表示成两个只包含一条非树边的环的对称差。可以证明不考虑这样的环，不会对答案造成影响。
时间复杂度\(\mathcal O(n\log n)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=1e5+1,M=2e5+1;
class DisjointSet {
private:
int anc[N];
int find(const int &x) {
return x==anc[x]?x:anc[x]=find(anc[x]);
}
public:
void reset(const int &n) {
for(register int i=1;i<=n;i++) anc[i]=i;
}
void merge(const int &x,const int &y) {
anc[find(x)]=find(y);
}
bool same(const int &x,const int &y) {
return find(x)==find(y);
}
};
DisjointSet s;
std::vector<std::pair<int,int> > e[N];
inline void add_edge(const int &u,const int &v,const int &id) {
e[u].push_back(std::make_pair(v,id));
e[v].push_back(std::make_pair(u,id));
}
struct Edge {
int u,v,id;
};
std::vector<Edge> edge;
int dep[N],par[N],top[N],size[N],son[N],dfn[N],id[N],cnt[M];
void dfs(const int &x,const int &par) {
size[x]=1;
::par[x]=par;
dep[x]=dep[par]+1;
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i].first;
if(y==par) continue;
id[y]=e[x][i].second;
dfs(y,x);
size[x]+=size[y];
if(size[y]>size[son[x]]) {
son[x]=y;
}
}
}
void dfs(const int &x) {
dfn[x]=++dfn[0];
top[x]=x==son[par[x]]?top[par[x]]:x;
if(son[x]) dfs(son[x]);
for(unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i].first;
if(y==par[x]||y==son[x]) continue;
dfs(y);
}
}
class SegmentTree {
#define _left <<1
#define _right <<1|1
#define mid ((b+e)>>1)
private:
int val[N<<2];
public:
void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const int &v) {
if(b==l&&e==r) {
val[p]+=v;
return;
}
if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),v);
if(r>mid) modify(p _right,mid+1,e,std::max(mid+1,l),r,v);
}
int query(const int &p,const int &b,const int &e,const int &x) const {
int ret=val[p];
if(b==e) return ret;
if(x<=mid) ret+=query(p _left,b,mid,x);
if(x>mid) ret+=query(p _right,mid+1,e,x);
return ret;
}
#undef _left
#undef _right
#undef mid
};
SegmentTree t;
inline int lca(int x,int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) {
std::swap(x,y);
}
x=par[top[x]];
}
return dep[x]<dep[y]?x:y;
}
inline int dist(const int &x,const int &y) {
const int z=lca(x,y);
return dep[x]+dep[y]-dep[z]*2;
}
inline void modify(int x,int y,const int &v) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) {
std::swap(x,y);
}
t.modify(1,1,dfn[0],dfn[top[x]],dfn[x],v);
x=par[top[x]];
}
if(dep[x]<dep[y]) std::swap(x,y);
if(x!=y) {
t.modify(1,1,dfn[0],dfn[y]+1,dfn[x],v);
}
}
int main() {
const int n=getint(),m=getint();
s.reset(n);
for(register int i=1;i<=m;i++) {
const int u=getint(),v=getint();
if(s.same(u,v)) {
edge.push_back((Edge){u,v,i});
continue;
}
s.merge(u,v);
add_edge(u,v,i);
}
for(register int i=1;i<=n;i++) {
if(dfn[i]) continue;
dfs(i,0);
dfs(i);
}
int tot=0;
const int k=edge.size();
for(register int i=0;i<k;i++) {
const int &u=edge[i].u,&v=edge[i].v;
if(dist(u,v)&1) {
modify(u,v,-1);
cnt[edge[i].id]--;
} else {
tot++;
modify(u,v,1);
cnt[edge[i].id]++;
}
}
for(register int i=1;i<=n;i++) {
cnt[id[i]]=t.query(1,1,n,dfn[i]);
}
int ans=0;
for(register int i=1;i<=m;i++) {
ans+=cnt[i]==tot;
}
printf("%d\n",ans);
return 0;
}