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

【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

5 5 5
4 3
1 3
5 4
2 3
4 2
5 4
3 2
1 3
4
1
3
5
4
1
5
1
2
3
1 2 1 1 2
1 1 5 2 2
1 4 1 2 3
1 5 4 2 2
1 4 1 1 3

Sample Output

2
2
2
2
3

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
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++;
	}
	templatevoid 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();}
	templatevoid 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;

queueq;
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(rrr)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;
vectors[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]