首页 > 代码库 > BZOJ 4771: 七彩树

BZOJ 4771: 七彩树

2024-09-09 01:13:44   209人阅读

4771: 七彩树

Time Limit: 5 Sec  Memory Limit: 256 MB
Submit: 289  Solved: 87
[Submit][Status][Discuss]

Description

给定一棵n个点的有根树，编号依次为1到n，其中1号点是根节点。每个节点都被染上了某一种颜色，其中第i个节
点的颜色为c[i]。如果c[i]=c[j]，那么我们认为点i和点j拥有相同的颜色。定义depth[i]为i节点与根节点的距离
，为了方便起见，你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面，你将面临m个问题。
每个问题包含两个整数x和d，表示询问x子树里且depth不超过depth[x]+d的所有点中出现了多少种本质不同的颜色
。请写一个程序，快速回答这些询问。

Input

第一行包含一个正整数T(1<=T<=500)，表示测试数据的组数。
每组数据中，第一行包含两个正整数n(1<=n<=100000)和m(1<=m<=100000)，表示节点数和询问数。
第二行包含n个正整数，其中第i个数为c[i](1<=c[i]<=n)，分别表示每个节点的颜色。
第三行包含n-1个正整数，其中第i个数为f[i+1](1<=f[i]<i)，表示节点i+1的父亲节点的编号。
接下来m行，每行两个整数x(1<=x<=n)和d(0<=d<n)，依次表示每个询问。
输入数据经过了加密，对于每个询问，如果你读入了x和d，那么真实的x和d分别是x xor last和d xor last，
其中last表示这组数据中上一次询问的答案，如果这是当前数据的第一组询问，那么last=0。
输入数据保证n和m的总和不超过500000。

Output

对于每个询问输出一行一个整数，即答案。

Sample Input

1
5 8
1 3 3 2 2
1 1 3 3
1 0
0 0
3 0
1 3
2 1
2 0
6 2
4 1

Sample Output

1
2
3
1
1
2
1
1

HINT

Source

By Claris

分析：

看到HZ某位大佬(不认识...)在写此题...一时兴起也去写...然后TLE了N多年...

这题和之前考试的某题很像...第一想法就是把相同颜色的点拎出来分别考虑对答案的影响，可以把相同颜色的每个点+1，然后把这些点按照dfs序排序，相邻的点LCA-1(据说这叫树链的并...)...然后发现有深度的限制...懵逼了...

然后跑去膜拜题解...

诶...可以主席树...因为有深度的限制，并且我们是在线段树上维护权值，所以我们把点按照dep排序，然后一个一个修改...主席树的下标就是dfs序，子树的查询就是区间查询...

但是发现这样怎么去维护LCA呢...因为要求有序，所以我们可以用set来维护相同颜色的节点...如果把一个点加入集合之后这个点前驱为x，后继为y，那么我们去修正，把xy的LCA+1，然后x和当前点的LCA-1，当前点和y的LCA-1...

需要注意的是不要memset...我把主席树的权值数组memset了...(10000000...不TLE才鬼...)T了一屏...

代码：

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<set>//by NeighThorn#define min(a,b) a<b?a:busing namespace std;const int maxn=100000+5,maxm=10000000+5;int ls[maxm],rs[maxm],sum[maxm],root[maxn],son[maxn],siz[maxn],top[maxn];int n,m,ans,cas,cnt,tim,tot,c[maxn],hd[maxn],to[maxn],fa[maxn][25],nxt[maxn],dfn[maxn],dep[maxn],End[maxn],node[maxn];/*struct cmp{	 bool operator () (int a,int b){		return dfn[a]<dfn[b];	}};set<int,cmp> v[maxn];set<int,cmp>::iterator it;*/typedef pair<int,int> P;set<P> v[maxn];set<P>::iterator it,l,s;inline int read(void){	char ch=getchar();int x=0,f=1;	while(!(ch>=‘0‘&&ch<=‘9‘)){		if(ch==‘-‘) f=-1;		ch=getchar();	}	while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();	return f*x;}inline void add(int x,int y){	to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;}inline void dfs(int x){	siz[x]=1;	for(int i=hd[x];i!=-1;i=nxt[i]){		fa[to[i]][0]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);		siz[x]+=siz[to[i]];		if(siz[son[x]]<siz[to[i]])			son[x]=to[i];	}}inline void dfs2(int x,int t){	dfn[x]=++tim;top[x]=t;	if(son[x]==0){		End[x]=tim;return;	}	dfs2(son[x],t);	for(int i=hd[x];i!=-1;i=nxt[i])		if(to[i]!=son[x])			dfs2(to[i],to[i]);	End[x]=tim;son[x]=0;}inline int LCA(int x,int y){	while(top[x]!=top[y]){		if(dep[top[x]]<dep[top[y]])			swap(x,y);		x=fa[top[x]][0];	}	if(dep[x]<dep[y])		swap(x,y);	return y;}inline void change(int l,int r,int pos,int val,int x,int &y){	y=++tot;sum[y]=sum[x]+val;	if(l==r)		return;	int mid=(l+r)>>1;ls[y]=ls[x];rs[y]=rs[x];	if(pos<=mid)		change(l,mid,pos,val,ls[x],ls[y]);	else		change(mid+1,r,pos,val,rs[x],rs[y]);	}inline int query(int l,int r,int y,int L,int R){	if(l==L&&R==r)		return sum[y];	int mid=(l+r)>>1;	if(R<=mid)		return query(l,mid,ls[y],L,R);	else if(L>mid)		return query(mid+1,r,rs[y],L,R);	else		return query(l,mid,ls[y],L,mid)+query(mid+1,r,rs[y],mid+1,R);}inline bool cmp(int x,int y){	return dep[x]<dep[y];}signed main(void){//	freopen("paint.in","r",stdin);//	freopen("paint.out","w",stdout);	cas=read();	while(cas--){		memset(hd,-1,sizeof(hd));		n=read(),m=read();cnt=0;		for(int i=1;i<=n;i++)			c[i]=read(),node[i]=i;		for(int i=2,x;i<=n;i++)			x=read(),add(x,i);		fa[1][0]=1;dep[1]=0;tim=tot=0;dfs(1);ans=0;dfs2(1,1);		sort(node+1,node+n+1,cmp);root[0]=0;		for(int i=1,x,y;i<=n;i++){			x=node[i];y=node[i-1];			change(1,n,dfn[x],1,root[dep[y]],root[dep[x]]);			if(!v[c[x]].empty()){				v[c[x]].insert(P(dfn[x],x));				it=v[c[x]].find(P(dfn[x],x));it--;s=it;				it=v[c[x]].find(P(dfn[x],x));it++;l=it;				if(l!=v[c[x]].end()&&s!=v[c[x]].end()) change(1,n,dfn[LCA(l->second,s->second)], 1,root[dep[x]],root[dep[x]]);				if(l!=v[c[x]].end())                   change(1,n,dfn[LCA(x        ,l->second)],-1,root[dep[x]],root[dep[x]]);				if(s!=v[c[x]].end())                   change(1,n,dfn[LCA(s->second,x        )],-1,root[dep[x]],root[dep[x]]);			}			else				v[c[x]].insert(P(dfn[x],x));		}		for(int i=1;i<=n;i++)			v[i].clear();		for(int i=1,x,d;i<=m;i++){			x=read(),d=read();x^=ans,d^=ans;			printf("%d\n",ans=query(1,n,root[min(dep[x]+d,dep[node[n]])],dfn[x],End[x]));		}	}	return 0;}

　　

By NeighThorn

 

BZOJ 4771: 七彩树


联系
我们