题目概述

CF1444C

解题报告

首先我们对于每个相同颜色的块，求出是否存在奇环，如果存在那么这种颜色显然不能选。

排除了不能选的颜色之后，我们发现只有有边相连的两种颜色才有可能违法，因此会违法的颜色对最多只有 $m$ 个！

因此考虑求出违法的颜色对然后用总方案减去。

对于相同颜色的块，如果不违法，那么肯定能够01交替进行编号。如果对于两对点 $(x_1,y_1),(x_2,y_2)$ ，$x_1,x_2$ 在 $c_x$ 颜色块中，$y_1,y_2$ 在 $c_y$ 颜色块中，并且 $x_1,y_1$ 编号相同，$x_2,y_2$ 编号不同，那么就违法了。

因此用并查集按秩合并进行奇环以及编号相同性的判断，每次处理完一个颜色对的所有边之后回滚清空并查集。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=500000,maxm=500000,maxk=500000,maxt=(maxn<<1)*2;

int n,m,K,c[maxn+5],fat[(maxn<<1+5)],rk[(maxn<<1)+5];LL ans;
pair<int,int> e[maxm+5];bool vis[maxk+5];
int E,lnk[maxn+5],nxt[(maxm<<1)+5],son[(maxm<<1)+5];
int ID[maxn+5],tp[maxn+5],top;pair<int*,int> stk[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline bool cmp(const pair<int,int> &a,const pair<int,int> &b){
    return c[a.fr]<c[b.fr] || c[a.fr]==c[b.fr] && c[a.sc]<c[b.sc];
}
int getfa(int x) {return x==fat[x]?x:getfa(fat[x]);}
inline void Change(int* x,int y) {stk[++top]=mp(x,*x);*x=y;}
bool Merge(int x,int y){
    x=getfa(x);y=getfa(y);if (x==y) return false;
    if (rk[x]<rk[y]) swap(x,y);Change(&fat[y],x);
    if (rk[x]==rk[y]) Change(&rk[x],rk[x]+1);
    return true;
}
void Pop() {while (top) *stk[top].fr=stk[top].sc,top--;}
void DFS(int who,int x,int C,int pre=0,int p=0){
    if (~tp[x]) return;ID[x]=who;tp[x]=p;
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) DFS(who,son[j],C,x,p^1);
}
int main(){
    freopen("C.in","r",stdin);freopen("C.out","w",stdout);
    readi(n);readi(m);readi(K);
    for (int i=1;i<=n;i++) readi(c[i]),tp[i]=-1;
    for (int i=1;i<=m;i++){
        readi(e[i].fr);readi(e[i].sc);
        if (c[e[i].fr]==c[e[i].sc]) Add(e[i].fr,e[i].sc),Add(e[i].sc,e[i].fr);
        if (c[e[i].fr]>c[e[i].sc]) swap(e[i].fr,e[i].sc);
    }
    sort(e+1,e+1+m,cmp);
    for (int i=1;i<=(n<<1);i++) fat[i]=i,rk[i]=0;
    for (int i=1,k;i<=m;i++)
        if (c[e[i].fr]==c[e[i].sc] && !vis[k=c[e[i].fr]]){
            int x=e[i].fr,y=e[i].sc;
            if (!Merge(x,y+n)) vis[k]=true;
            if (!Merge(y,x+n)) vis[k]=true;
        }
    for (int i=1;i<=K;i++) ans+=!vis[i];ans=ans*(ans-1)>>1;
    for (int i=1;i<=n;i++) if (!vis[c[i]]) DFS(i,i,c[i]);
    for (int i=1;i<=(n<<1);i++) fat[i]=i,rk[i]=0;top=0;
    for (int i=1,j;i<=m;i=j){
        for (j=i;j<=m && c[e[i].fr]==c[e[j].fr] && c[e[i].sc]==c[e[j].sc];j++);
        if (vis[c[e[i].fr]] || vis[c[e[i].sc]] || c[e[i].fr]==c[e[i].sc]) continue;
        Pop();
        for (int k=i;k<j;k++){
            int x=e[k].fr,y=e[k].sc,fx=ID[e[k].fr],fy=ID[e[k].sc];
            tp[x]==tp[y]?(Merge(fx,fy),Merge(fx+n,fy+n)):(Merge(fx,fy+n),Merge(fx+n,fy));
            if (getfa(fx)==getfa(fx+n) || getfa(fy)==getfa(fy+n)) {ans--;break;}
        }
    }
    printf("%lld\n",ans);return 0;
}