好像确实有维护动态图的方法……但是可能是考场上写不出的那种……
考虑离线,建出可持久化树,如果用并查集维护图的连通性,会发现不能维护删边,因此我们考虑如何只进行加边操作和撤销。
可持久化树中,如果在 $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$ :
由于保证了加边和删边都合法且不重复,因此入栈和出栈时就可以确定区间。
而刚开始给的边可以认为是刚进入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;
}