BZOJ4771 - 七彩樹——貪心、思維、主席樹

#4771. 七彩樹

題解

子樹内的顔色個數，感覺不好做啊。如果不看深度的限制，轉換到 d f s \rm dfs dfs 序上，那麼就是經典的區間内顔色種類數的問題，直接用線段樹上節點維護 s e t \rm set set 再 O ( log ⁡ 2 n ) O(\log^2n) O(log2n) 查詢即可。

有了深度限制就不好辦了。如果仍然按照上面的思路，怎麼也得用可持久化線段樹套可持久化 T r e a p \rm Treap Treap 來維護，常數極大，而且空間可能炸。

睿智的永神OneInDark曾說：

明明本質就是另一個問題，但時間複雜度不能通過，為什麼？因為它是特殊化的情況。——《怎樣解題》

這啟發我們：此題一定還有可用性質！

我們發現所有的問題并不是詢問深度在某個區間的點，而是深度小于等于某個值。并且，我們詢問的是子樹，不是一般的區間，有十厘清晰的樹形包含關系。

于是我們可以考慮按深度為時間軸建立主席樹，優先加入深度更小的點，那麼所有新加入的點隻能對子樹内還沒有該點顔色的祖先産生貢獻。這個可以對每一種顔色用一個 s e t \rm set set 維護已加入主席樹的點的 d f s \rm dfs dfs 序，然後每次加入一個點，通過與其前驅後繼求 l c a \rm lca lca 找到往上的第一個子樹内已有此顔色的祖先。設這個祖先的 d f s \rm dfs dfs 序為 a a a，加入點的 d f s \rm dfs dfs 序為 b b b，我們線上段樹上将 a a a 處-1， b b b 處+1。這樣做的效果就是，所有在祖先 a a a 及以上的祖先查詢時的結果不變，而祖先 a a a 以下的祖先（包括該節點本身）都會正常地加上1的貢獻。

經過這樣一番處理，查詢時就隻用找到某一棵主席樹詢問一個區間和就完了。總複雜度隻有 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

代碼

#include<cstdio>//JZM yyds!!
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define uns unsigned
#define ll long long
#define ull uns ll
#define MAXN 200005
#define INF 1e17
#define lowbit(x) ((x)&(-(x)))
#define IF (it->first)
#define IS (it->second)
using namespace std;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return f?x:-x;
}
int n,m,c[MAXN];

struct itn{
	int ls,rs,a;itn(){}
	itn(int A){a=A,ls=rs=0;}
}t[MAXN<<5];
int IN;
inline void add(int x,int y,int l,int r,int z,int d){
	t[y]=t[x],t[y].a+=d;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(z<=mid)t[y].ls=++IN,add(t[x].ls,t[y].ls,l,mid,z,d);
	else t[y].rs=++IN,add(t[x].rs,t[y].rs,mid+1,r,z,d);
	t[y].a=t[t[y].ls].a+t[t[y].rs].a;
}
inline int query(int x,int l,int r,int a,int b){
	if(!x)return 0;
	if(l>=a&&r<=b)return t[x].a;
	int mid=(l+r)>>1,res=0;
	if(a<=mid)res+=query(t[x].ls,l,mid,a,b);
	if(b>mid)res+=query(t[x].rs,mid+1,r,a,b);
	return res;
}

set<int>st[MAXN];
set<int>::iterator it;
int rt[MAXN];
vector<int>ad[MAXN];
int dep[MAXN],hd[MAXN],dh[MAXN],tl[MAXN],PN;
int fa[MAXN][25];
vector<int>G[MAXN];
inline void dfs(int x){
	dep[x]=dep[fa[x][0]]+1;
	hd[x]=++PN,dh[PN]=x;
	for(int i=1;i<=18;i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(uns i=0;i<G[x].size();i++){
		int v=G[x][i];
		fa[v][0]=x,dfs(v);
	}
	tl[x]=PN;
}
inline int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=18;i>=0;i--)
		if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
	if(u!=v){
		for(int i=18;i>=0;i--)
			if(fa[u][i]!=fa[v][i])
				u=fa[u][i],v=fa[v][i];
		u=fa[u][0];
	}return u;
}
signed main()
{
	for(int T=read();T--;){
		n=read(),m=read();
		IN=0,PN=0;
		for(int i=1;i<=n;i++){
			G[i].clear(),c[i]=read();
			memset(fa[i],0,sizeof(fa[i]));
			st[i].clear(),rt[i]=0,ad[i].clear();
		}
		for(int i=2;i<=n;i++)G[read()].push_back(i);
		dfs(1);
		for(int i=1;i<=n;i++)
			ad[dep[i]].push_back(i);
		for(int i=1;i<=n;i++){
			int A=rt[i-1];rt[i]=A;
			for(uns j=0;j<ad[i].size();j++){
				int u=ad[i][j],o=c[u],lc=0;
				it=st[o].lower_bound(hd[u]);
				if(it!=st[o].end()){
					int pc=lca(dh[*it],u);
					if(dep[pc]>dep[lc])lc=pc;
				}
				if(it!=st[o].begin()){it--;
					int pc=lca(dh[*it],u);
					if(dep[pc]>dep[lc])lc=pc;
				}
				st[o].insert(hd[u]);
				if(lc>0){
					add(rt[i],A=++IN,1,n,hd[lc],-1);
					rt[i]=A;
				}
				add(rt[i],A=++IN,1,n,hd[u],1);
				rt[i]=A;
			}
		}
		int las=0;
		while(m--){
			int x=read()^las,d=dep[x]+(read()^las);
			d=min(d,n);
			las=query(rt[d],1,n,hd[x],tl[x]);
			printf("%d\n",las);
		}
	}
	return 0;
}