Link

题意:

有n(n<=20000)个小球，最开始都未被染色。

进行m(m<=20000)次操作，操作分为2种类型。

0.回到第x次操作的状态

1.将小球x和y所在的集合合并

然后进行k(k<=20000)次染色操作。

第i次染色操作将时间ti时xi所在连通块中最多zi个小球染色。

如果一个小球被染色了，那么任意时刻它都被染色了。

求最多能将多少小球染色。

分析:

很容易想到网络流的做法，但是一般的建图方法的点数和边数都无法接受。

考虑用可持久化的思想优化网络流建图。

首先处理连通性时我们会用到用主席树实现的可持久化并查集。

注意，这时不能使用路径压缩，要按秩合并来优化。

然后可以发现可持久化并查集就可以来优化建图了。

我们只考虑叶子。

S向最初版本的每个叶子连容量1的边。

每次更新时将历史版本向当前版本连容量为+∞的边；

合并时，向集合代表元连容量为+∞的边。

每次染色时，找到ti版本xi所在集合的代表元，向T连容量为zi的边。

然后跑最大流就行了。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define S 1
#define T 2
#define inf 0x7f7f7f7f
#define gap(i) e[i].c-e[i].f
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=80005;

int Id=2;

typedef struct node*star;

struct node{
	int f,id,sz;
	star ch[2];
}pool[MAXN*20];
star tail=pool;

inline star query(star x,int l,int r,int pos){
	while(l<r){
		int mid=(l+r)>>1,d=pos>mid;
		if(d)l=mid+1; else r=mid;
		x=x->ch[d];
	}
	return x;
}

int n,m,k,Head[MAXN];

star rt[MAXN];

struct edge{
	int t,c,f,n;
	edge(int t=0,int c=0,int n=0):
		t(t),c(c),f(0),n(n){}
}e[MAXN<<2];
int head[MAXN],tot=1;
inline void AddEdge(int s,int t,int c=1){
	e[++tot]=edge(t,c,head[s]),head[s]=tot;
	e[++tot]=edge(s,0,head[t]),head[t]=tot;
}

void build(star&x,int l,int r){
	x=tail++;
	if(l==r){
		x->f=l,x->sz=1;
		AddEdge(S,x->id=++Id);
		return;
	}
	int mid=(l+r)>>1;
	build(x->ch[0],l,mid);
	build(x->ch[1],mid+1,r);
}

void update(star&y,star x,int l,int r,int t,int f,int v){
	y=++tail; *y=*x;
	if(l==r){
		y->f=f,y->sz+=v;		
		AddEdge(x->id,y->id=++Id,inf);		
		return;
	}
	int mid=(l+r)>>1,d=t>mid;
	if(d)l=mid+1; else r=mid;
	update(y->ch[d],x->ch[d],l,r,t,f,v);
}

star find(int idx,int x){
	star res=query(rt[idx],1,n,x);
	return res->f==x?res:find(idx,res->f);
}

inline void Init(){
	Scan(n),Scan(m),Scan(k);
	build(rt[0],1,n);
}

inline void Merge(int idx,int x,int y){
	star fx=find(idx,x);
	star fy=find(idx,y);
	if(fx->f==fy->f)return;
	if(fx->sz>fy->sz)swap(fx,fy);
	update(rt[idx],rt[idx],1,n,fx->f,fy->f,0);
	update(rt[idx],rt[idx],1,n,fy->f,fy->f,fx->sz);
	fx=query(rt[idx],1,n,fx->f);
	fy=query(rt[idx],1,n,fy->f);
	AddEdge(fx->id,fy->id,inf);
}

int d[MAXN],p[MAXN],q[MAXN];

int cur[MAXN],g[MAXN];

inline int isap(int s,int t,int n){
	rep(i,1,n+1)d[i]=n;
	int tail=1;
	q[1]=t; d[t]=0;
	rep(h,1,tail+1){
		int x=q[h];
		++g[d[x]],cur[x]=head[x];
		for(int i=head[x],y;i;i=e[i].n)	
			if(!e[i].c&&d[y=e[i].t]==n){
				d[y]=d[x]+1;
				q[++tail]=y;
			}
	}
	int flow=0,x=s,a,f;
	while(d[s]<n){
		if(x==t){
			a=inf;
			for(int i=t;i!=s;i=e[p[i]^1].t)
				a=min(a,gap(p[i]));
			for(int i=t;i!=s;i=e[p[i]^1].t)
				e[p[i]].f+=a,e[p[i]^1].f-=a;
			flow+=a;
			x=s;
		}
		f=1;
		for(int&i=cur[x];i;i=e[i].n)
			if(gap(i)&&d[x]==d[e[i].t]+1){
				f=0;
				p[x=e[i].t]=i;
				break;
			}
		if(f){
			if(!(--g[d[x]]))break;
			f=n-1;
			for(int i=head[x];i;i=e[i].n)
				if(gap(i))f=min(f,d[e[i].t]);
			++g[d[x]=f+1];
			cur[x]=head[x];
			if(x!=s)x=e[p[x]^1].t;
		}
	}
	return flow;
}

inline void Solve(){
	rep(i,1,m+1){
		rt[i]=rt[i-1];
		int t,x,y; 
		Scan(t),Scan(x);
		if(t)Scan(y),Merge(i,x,y);
		else rt[i]=rt[x];	
	}
	rep(i,0,k){
		int x,y,w;
		Scan(x),Scan(y),Scan(w);
		star f=find(x,y);
		AddEdge(f->id,T,w);
	}
	printf("%d\n",isap(S,T,Id));
}

int main(){
	freopen("link.in","r",stdin);
	freopen("link.out","w",stdout);
	Init(); Solve(); return 0;
}