CF19E Fairy(树上差分）

题目描述

很久很久以前，有一个仙女叫做A。有一天一个少年B找到她，并且请求她预测他的未来。仙女看着她的水晶球，说这位少年不久将遇见世界上最美丽的公主，并且将迎娶她为妻。然后仙女在一张纸上画了n个点，并把它们分为几个板块，每个板块以一些点为始，另一些点为终。画完这幅画，仙女要求少年擦掉之上的一个板块。然后她尝试给每个点画上红色或蓝色，让纸上没有板块有和它的结尾颜色一样的点。如果她能做到，这个预言将会成真。B想邂逅世界上最美丽的公主，所以他想要你帮助他。找到所有能帮助他邂逅公主的板块。

输入输出格式：

输入格式：

输入文件的第一行有两个整数：n——点数；m:板块个数。

接下来的m行有板块的描述。每一个描述有两个整数，用空格隔开——v,u——各点的编号（index），由此板块连接。没有板块在描述中会被描述两次。

输出格式：

输出文件的第一行输出数字k——答案中板块的数量。输出文件的第二行输出k个数字，以空格隔开————每个板块的编号，升序排列。每个编号只应被输出一次。板块从1开始编号，以输入的顺序为序。

题解

因为二分图没有奇环，我们就把奇环删掉就行了。

实际上需要分情况讨论：

当没有奇环时，随便删掉一条边即可。

当只有一个奇环时，删掉这个奇环上没有被偶环覆盖的边就行（因为把一个奇环和一个偶环的公共边删去还是一个奇环）

当有多条奇环时，删掉被所有奇环覆盖的且不被偶环覆盖的边。

代码细节很多具体看代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=500000;
int n,m,sum,ans,cnt;
int f[maxn],to[maxn<<1],next[maxn<<1],book[maxn<<1],head[maxn],pa[maxn],pb[maxn],vis[maxn],dep[maxn];
int fa[maxn][31],Log[maxn],pc[maxn],s1[maxn],s0[maxn],from[maxn],bok[maxn];
inline void add(int a,int b){
    to[++cnt]=b;
    next[cnt]=head[a];
    head[a]=cnt;
}
void dfs1(int x){
    vis[x]=1;
    for(int i=head[x];i;i=next[i])  
        if(!vis[to[i]])
            book[i]=1,fa[to[i]][0]=x,dep[to[i]]=dep[x]+1,from[to[i]]=(i>>1),dfs1(to[i]);
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=30;i>=0;i--){
        if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    }
    if(u==v)return v;
    for(int i=30;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];v=fa[v][i];
        }
    }
    return fa[u][0];
}
void dfs2(int x){
    for(int i=head[x];i;i=next[i])  
        if(book[i])  
            dfs2(to[i]),s1[x]+=s1[to[i]],s0[x]+=s0[to[i]];
}
int main()
{
    scanf("%d%d",&n,&m);
    cnt=1;
    int i,j;
    for(i=1;i<=m;i++){
        scanf("%d%d",&pa[i],&pb[i]);add(pa[i],pb[i]);add(pb[i],pa[i]);
    }
    for(i=1;i<=n;i++)    if(!vis[i]) dep[i]=1,dfs1(i);
    for(int i=1;i<=30;i++)
        for(int j=1;j<=n;j++){
            fa[j][i]=fa[fa[j][i-1]][i-1];
        }
    for(i=1;i<=m;i++)    
    if(!book[i*2]&&!book[i*2+1]){
        pc[i]=lca(pa[i],pb[i]);
        if(!((dep[pa[i]]^dep[pb[i]])&1))sum++,s1[pa[i]]++,s1[pb[i]]++,s1[pc[i]]-=2;
        else s0[pa[i]]++,s0[pb[i]]++,s0[pc[i]]-=2;
    }
    for(i=1;i<=n;i++)if(dep[i]==1)dfs2(i);
    if(!sum){
        printf("%d\n",m);
        for(i=1;i<=m;i++)printf("%d ",i);
        return 0;
    }
    if(sum==1)
        for(i=1;i<=m;i++)
            if(!book[i*2]&&!book[i*2+1]&&!((dep[pa[i]]^dep[pb[i]])&1))bok[i]=1,ans++;
    for(i=1;i<=n;i++)
        if(s1[i]==sum&&!s0[i])bok[from[i]]=1,ans++;
    printf("%d\n",ans);
    for(i=1;i<=m;i++)
        if(bok[i])printf("%d ",i);
    return 0;
}