【2021集训队出题】树上的孤独

2023-11-22 09:01:57

【2021集训队出题】树上的孤独

by AmanoKumiko

Description

给出\(n\)个点的树\(A\)，\(m\)个点的树\(B\)，都以\(1\)为根，每个点有一种颜色

有\(q\)次询问，每次询问给出一个\(P\)

若\(P=1\)，读入\(P1,P2,P3,P4\)

令\(D1=lstans\bigoplus P3,D2=lstans\bigoplus P4\)

输出\(A\)中\(P1\)子树内距离不超过\(D1\)和\(B\)中\(P2\)子树内距离不超过\(D2\)的节点中一共有多少种颜色

若\(P=2\)，读入\(S1,S2\)

将\(A\)中\(S1\)的颜色改为\(S2\)

Input

第一行读入三个整数\(n,m,q\)

接下来\(n-1\)行读入树\(A\)

接下来\(m-1\)行读入树\(B\)

接下来\(n\)行读入树\(A\)中颜色

接下来\(m\)行读入树\(B\)中颜色

最后读入\(q\)个询问

Output

每次询问输出一行一个数表示答案

Sample Input

Sample Output

Data Constraint

\(1\le n\le 20,1\le m\le 2*10^5,1\le q\le 10^6\)

\(1\le P1\le n,1\le P2\le m,1\le P3,P4\le 2*10^5\)

\(1\le S1\le n,1\le c,S2\le m\)

Solution

只能说在线离线这块给出题人整明白了

看起来这是一个在线问题，但实际上他是一个在线离线问题

首先答案等于\(c(A)+c(B)-c(A∩B)\)

对于\(c(A)\)，暴力算

对于\(c(B)\)，用数组记录每个颜色的最浅深度，然后通过重链剖分+启发式合并+主席树完成

对于最后面那部分，考虑对于每个询问，记录当前\(A\)中所有的颜色，然后挂到相对应的节点上去

这样，在算第二部分答案的时候就可以顺便完成

达到了\(O(nq+mlog^2m)\)的优秀复杂度

Code

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse") 
#pragma GCC diagnostic error "-std=c++14" 
#pragma GCC diagnostic error "-fwhole-program" 
#pragma GCC diagnostic error "-fcse-skip-blocks" 
#pragma GCC diagnostic error "-funsafe-loop-optimizations" 
#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")
#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 30
#define M 200010
#define Q 1000010
#define S 40000010

namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
		return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	}
	template<class T>void read(T&x){
		x=0;char c=gc();
		for(;c<'0'||c>'9';c=gc());
		for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b;}
	inline void pc(char x){*t++=x;if(t-b==sz)flush();}
	template<class T>void write(T x,char c='\n'){
		if(x==0)pc('0');int t=0;
		for(;x;x/=10)p[++t]=x%10+'0';
		for(;t;--t)pc(p[t]);pc(c);
	}
	struct F{~F(){flush();}}f;
}
using IO::read;
using IO::write;

queue<int>q;
int n,m,qt,u,v,lstans,cnow[M],cb,cfst[N],Lim,wh[M],in[M];
int size[M],son[M],d[M],lst[M];
struct tree{
	int root[S],cnt,sum[S],ls[S],rs[S];
	int build(int l,int r,int pos,int val,int ed){
		int x=++cnt;
		sum[x]=sum[ed]+val;
		if(l==r)return x;
		ls[x]=ls[ed];rs[x]=rs[ed];
		int mid=l+r>>1;
		if(pos<=mid)ls[x]=build(l,mid,pos,val,ls[ed]);
		else rs[x]=build(mid+1,r,pos,val,rs[ed]);
		return x;
	}
	int query(int x,int l,int r,int ll,int rr){
		if(!x)return 0;
		if(r<ll||l>rr)return 0;
		if(l>=ll&&r<=rr)return sum[x];
		int mid=l+r>>1;
		return query(ls[x],l,mid,ll,rr)+query(rs[x],mid+1,r,ll,rr);
	}
}t;
struct node{
	int en[M*2],next[M*2],last[M],tot,fa[M],col[M];
	void add(int x,int y){en[++tot]=y;next[tot]=last[x];last[x]=tot;}
}e1,e2;
struct mode{int kind,P1,P2,P3,P4;}ask[Q];
struct col{int v[N];}Ac,Bc;
vector<col>s[M],p[M];

void deal_first1(int now,int pre){
	e1.fa[now]=pre;
	for(int i=e1.last[now];i;i=e1.next[i]){
		if(e1.en[i]!=pre)deal_first1(e1.en[i],now);
	}
}

void deal_first2(int now,int pre){
	e2.fa[now]=pre;size[now]=1;d[now]=d[pre]+1;
	for(int i=e2.last[now];i;i=e2.next[i]){
		if(e2.en[i]!=pre){
			deal_first2(e2.en[i],now);
			size[now]+=size[e2.en[i]];
			if(size[e2.en[i]]>size[son[now]])son[now]=e2.en[i];
		}
	}
}

void calc(int now){
	for(;;now=e2.fa[now]){
		t.root[now]=t.root[son[now]];
		q.push(now);
		for(int i=e2.last[now];i;i=e2.next[i]){
			if(e2.en[i]!=e2.fa[now]&&e2.en[i]!=son[now])q.push(e2.en[i]);
		}
		while(!q.empty()){
			int x=q.front();q.pop();
			if(lst[e2.col[x]]){
				if(d[x]<lst[e2.col[x]]){
					t.root[now]=t.build(1,m,lst[e2.col[x]],-1,t.root[now]);
					t.root[now]=t.build(1,m,d[x],1,t.root[now]);
					lst[e2.col[x]]=d[x];
				}
			}else{
				int p;
				lst[e2.col[x]]=d[x];
				t.root[now]=t.build(1,m,d[x],1,t.root[now]);
			}
			if(x==now)continue;
			for(int i=e2.last[x];i;i=e2.next[i]){
				if(e2.en[i]!=e2.fa[x])q.push(e2.en[i]);
			}
		}
		for(auto A:s[now]){
			fo(i,1,n)Bc.v[i]=lst[A.v[i]];
			p[now].push_back(Bc);
		}
		if(son[e2.fa[now]]!=now)break;
	}
	q.push(now);
	while(!q.empty()){
		int now=q.front();q.pop();
		lst[e2.col[now]]=0;
		for(int i=e2.last[now];i;i=e2.next[i]){
			if(e2.en[i]!=e2.fa[now])q.push(e2.en[i]);
		}
	}
}

void get(int now,int pre,int dis){
	if(!cnow[e1.col[now]])cb++;
	cnow[e1.col[now]]++;in[e1.col[now]]=1;
	for(int i=e1.last[now];i;i=e1.next[i]){
		if(e1.en[i]!=pre&&dis+1<=Lim)get(e1.en[i],now,dis+1);
	}
}

int main(){
	read(n);read(m);read(qt);
	fo(i,1,n-1)read(u),read(v),e1.add(u,v),e1.add(v,u);
	fo(i,1,m-1)read(u),read(v),e2.add(u,v),e2.add(v,u);
	fo(i,1,n)read(e1.col[i]),Ac.v[i]=cfst[i]=e1.col[i];
	fo(i,1,m)read(e2.col[i]);
	deal_first1(1,0);deal_first2(1,0);
	fo(i,1,qt){
		read(ask[i].kind);
		if(ask[i].kind==1){
			read(ask[i].P1);read(ask[i].P2);read(ask[i].P3);read(ask[i].P4);
			s[ask[i].P2].push_back(Ac); 
		}else{
			read(ask[i].P1);read(ask[i].P2);
			Ac.v[ask[i].P1]=ask[i].P2;
			e1.col[ask[i].P1]=ask[i].P2;
		}
	}
	fo(i,1,n)e1.col[i]=cfst[i];
	fo(i,1,m)if(!son[i])calc(i);
	fo(i,1,qt){
		if(ask[i].kind==1){
			ask[i].P3^=lstans;ask[i].P4^=lstans;Lim=ask[i].P3;
			fo(j,1,n)cnow[e1.col[j]]=in[e1.col[j]]=0;cb=0;
			get(ask[i].P1,e1.fa[ask[i].P1],0);
			cb+=t.query(t.root[ask[i].P2],1,m,d[ask[i].P2],d[ask[i].P2]+ask[i].P4);
			fo(j,1,n){
				int ss=s[ask[i].P2][wh[ask[i].P2]].v[j];
				int cc=p[ask[i].P2][wh[ask[i].P2]].v[j];
				if(in[ss]&&cc-d[ask[i].P2]<=ask[i].P4&&cc)in[ss]=0,cb--;
			}
			wh[ask[i].P2]++;
			write((lstans=cb));
		}else e1.col[ask[i].P1]=ask[i].P2;
	}
	return 0;
}

码农公寓