题目概述

Equivalence in Connectivity

解题报告

好像确实有维护动态图的方法……但是可能是考场上写不出的那种……

考虑离线，建出可持久化树，如果用并查集维护图的连通性，会发现不能维护删边，因此我们考虑如何只进行加边操作和撤销。

可持久化树中，如果在 $t$ 点加入了 $(x,y)$ 边，我们可以认为 $(x,y)$ 在 $t$ 的DFS序 $[in_t,out_t]$ 都出现了，而如果 $t$ 点是删边，则认为是把 $[in_t,out_t]$ 中的 $(x,y)$ 边删掉。因此实际上对于每条边，都可以拆成若干个连续的区间，表示含有这条边的区间。这样我们只需要利用线段树分治就可以实现只加边和撤销而不删边。

考虑如何维护区间，首先先给每条边都标号，记录 $last_i$ 表示 $i$ 边当前处理到的DFS序。做DFS，处理到 $t$ 点时，假设边的标号为 $i$ ：

• 加边：入栈时，将 $last_i$ 更新为 $in_t$ 。出栈时，说明 $last_i$ 到 $out_t$ 都含有 $i$ 边，加入线段树中。
• 删边：入栈时，说明 $last_i$ 到 $in_t-1$ 都含有 $i$ 边，加入线段树中。出栈时，将 $last_i$ 更新为 $out_t+1$ 。

由于保证了加边和删边都合法且不重复，因此入栈和出栈时就可以确定区间。

而刚开始给的边可以认为是刚进入DFS时的加边操作。

最后考虑如何比较两张图的连通性，可以使用这样的哈希：给每个点都随机一个权值，然后对于每个连通块 $i$ ，权值为 $sum_i\cdot MIN_i$ ，$sum_i$ 表示 $i$ 连通块所有点权值的异或，$MIN_i$ 表示 $i$ 连通块的最小值。一张图的权值为所有连通块权值的加和。

示例程序

#include<map>
#include<vector>
#include<random>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef unsigned long long ULL;
const int maxn=100000,maxm=200000,maxt=maxn<<2,maxp=5e6,BA=999917;

int te,K,n,m,X[maxn+5],Y[maxn+5];
mt19937_64 mrand(164984);
ULL ha[maxn+5];
int cnt;map<pair<int,int>,int> f;
int E,lnk[maxn+5],nxt[maxn+5],to[maxn+5];
struct Data {int x,y,fl;} q[maxn+5];
int lt[maxn+5],rt[maxn+5],who[maxn+5];
int lst[maxm+5];
vector< pair<int,int> > e[maxt+5];
ULL fat[maxn+5],rk[maxn+5],sum[maxn+5],MIN[maxn+5],HA;
int top;pair<ULL*,ULL> stk[maxp+5];
int ID[maxn+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);
}
struct fastO{
    int si;char buf[100000];
    fastO() {si=0;}
    void putc(char ch){
        if (si==100000) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    int len=0,buf[100];
    if (x<0) fo.putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    if (ch) fo.putc(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void Build(int L,int R,int p=1){
    e[p].clear();
    if (L==R) return;
    int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
}
void Insert(int L,int R,pair<int,int> k,int l=1,int r=K,int p=1){
    if (L==l && r==R) {e[p].push_back(k);return;}
    int mid=l+(r-l>>1);
    if (R<=mid) Insert(L,R,k,l,mid,p<<1); else if (L>mid) Insert(L,R,k,mid+1,r,p<<1|1);
    else Insert(L,mid,k,l,mid,p<<1),Insert(mid+1,R,k,mid+1,r,p<<1|1);
}
void DFS(int x){
    lt[x]=++lt[0];who[lt[0]]=x;
    if (x>1){
        int id=f[mp(q[x].x,q[x].y)];
        if (q[x].fl) lst[id]=lt[x];
        else if (lst[id]<lt[x]) Insert(lst[id],lt[x]-1,mp(q[x].x,q[x].y));
    }
    for (int j=lnk[x];j;j=nxt[j]) DFS(to[j]);
    rt[x]=lt[0];
    if (x>1){
        int id=f[mp(q[x].x,q[x].y)];
        if (q[x].fl && lst[id]<=rt[x]) Insert(lst[id],rt[x],mp(q[x].x,q[x].y));
        lst[id]=rt[x]+1;
    }
}
void Change(ULL *x,ULL y) {stk[++top]=mp(x,*x);*x=y;}
int getfa(int x) {return x==fat[x]?x:getfa(fat[x]);}
void Solve(int L,int R,int p=1){
    int lst=top;
    for (auto x:e[p]){
        int X=getfa(x.fr),Y=getfa(x.sc);
        if (X==Y) continue;
        if (rk[X]<rk[Y]) swap(X,Y);
        ULL now=HA;
        now-=MIN[Y]*sum[Y];
        now-=MIN[X]*sum[X];
        Change(&MIN[X],min(MIN[X],MIN[Y]));
        Change(&sum[X],sum[X]^sum[Y]);
        now+=MIN[X]*sum[X];
        Change(&fat[Y],X);
        if (rk[X]==rk[Y]) Change(&rk[X],rk[X]+1);
        Change(&HA,now);
    }
    if (L==R){
        ha[who[L]]=HA;
        while (top!=lst) *stk[top].fr=stk[top].sc,top--;
        return;
    }
    int mid=L+(R-L>>1);
    Solve(L,mid,p<<1);Solve(mid+1,R,p<<1|1);
    while (top!=lst) *stk[top].fr=stk[top].sc,top--;
}
inline bool cmp(const int &i,const int &j) {return ha[i]<ha[j];}
int main(){
    for (readi(te);te;te--){
        readi(K);readi(n);readi(m);
        cnt=0;f.clear();
        for (int i=1;i<=m;i++){
            readi(X[i]);readi(Y[i]);
            f[mp(X[i],Y[i])]=++cnt;
        }
        E=0;for (int i=1;i<=K;i++) lnk[i]=0;
        for (int i=2;i<=K;i++){
            int fa;readi(fa);
            char ch=readc();while (!islower(ch)) ch=readc();
            int x,y;readi(x);readi(y);
            if (!f.count(mp(x,y))) f[mp(x,y)]=++cnt;
            Add(fa,i);q[i]=(Data){x,y,ch=='a'};
        }
        for (int i=1;i<=m;i++) lst[i]=1;
        Build(1,K);lt[0]=0;DFS(1);
        for (int i=1;i<=m;i++) if (lst[i]<=K) Insert(lst[i],K,mp(X[i],Y[i]));
        HA=0;
        for (int i=1;i<=n;i++)
            fat[i]=i,rk[i]=0,sum[i]=mrand(),MIN[i]=i,HA+=sum[i]*i;
        Solve(1,K);
        for (int i=1;i<=K;i++) ID[i]=i;
        sort(ID+1,ID+1+K,cmp);
        int tot=0;
        for (int i=1,j;i<=K;i=j){
            for (j=i+1;j<=K && ha[ID[i]]==ha[ID[j]];j++);
            tot++;
        }
        writei(tot);
        for (int i=1,j;i<=K;i=j){
            for (j=i+1;j<=K && ha[ID[i]]==ha[ID[j]];j++);
            writei(j-i,0);
            for (int k=i;k<j;k++) fo.putc(' '),writei(ID[k],0);
            fo.putc('\n');
        }
    }
    return 0;
}