[bzoj省选十连测推广赛2]T2七彩树
发布日期:2021-08-14 10:59:19 浏览次数:1 分类:技术文章

本文共 2776 字,大约阅读时间需要 9 分钟。

抄自:

当时看了就不会,看了别人的题解不懂怎么维护,最后抄了个代码.......

给定一棵n个点的树,每个点有颜色。m次询问,每次询问一个节点子树中深度和这个点深度之差<=d的点的颜色数量。多组数据,每组n,m<=10^5,总共小于500000

题解:如果不考虑深度,我们可以把相同颜色的节点按照dfs序排序,然后相邻节点在lca处-1,这样求子树和就可以求出答案了。考虑深度,我们就用主席树以深度为时间戳来维护呗。感觉看了原作者的代码学到了很多,原作者用set来维护相邻的相同颜色的节点真的妙。

#include
#include
#include
#include
#include
#include
#define mp(x,y) make_pair#define pa pair
#define itr set
>::iterator#define MAXN 100000using namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;} int n,m,cnt,cc,dfn,head[MAXN+5],p[MAXN+5];int fa[MAXN+5][25],rt[MAXN+5],dep[MAXN+5],nl[MAXN+5],nr[MAXN+5],col[MAXN+5];struct TREE{ int l,r,x,lt,rt;}T[10000005];vector
v[MAXN+5];set
ev[MAXN+5];struct edge{ int to,next;}e[2*MAXN+5];inline void ins(int f,int t){e[++cc].next=head[f];head[f]=cc;e[cc].to=t;}bool cmp(int x,int y){ return nl[x]
>=1,++i)if(th&1)x=fa[x][i]; if(x==y)return x; for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0];} void renew(int x0,int&x,int k,int ad,int l,int r){ // cout<<"renew"<
<<" "<
<<" "<
<<" "<
<<" "<
<<" "<
<
>1; if(k<=mid)renew(T[x0].lt,T[x].lt,k,ad,l,mid); else renew(T[x0].rt,T[x].rt,k,ad,mid+1,r);} int query(int k,int l,int r){ //cout<<"query"<
<<" "<
<<" "<
<
>1; if(r<=mid)return query(T[k].lt,l,r); else if(l>mid) return query(T[k].rt,l,r); else return query(T[k].lt,l,mid)+query(T[k].rt,mid+1,r);} int main(){ int T=read(); for(int i=1;i<=T;i++) { cnt=cc=dfn=0;for(int i=1;i<=n;i++)v[i].clear(); memset(head,0,sizeof(head));memset(rt,0,sizeof(rt));n=read();m=read(); for(int i=1;i<=n;i++){col[i]=read();} for(int i=2;i<=n;i++){fa[i][0]=read();ins(fa[i][0],i);} dfs(1,1); for(int i=1;i<20;i++)for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1]; for(int i=1;i<=n;i++)p[i]=i;sort(p+1,p+n+1,cmp2); for(int i=1;i<=n;i++) { int x=p[i],y=p[i-1]; renew(rt[dep[y]],rt[dep[x]],nl[x],1,1,n); if(ev[col[x]].empty()){ev[col[x]].insert(pa(nl[x],x));continue;} ev[col[x]].insert(pa(nl[x],x)); itr it=ev[col[x]].find(pa(nl[x],x)); itr a=--it;it=ev[col[x]].find(pa(nl[x],x));itr b=++it; if(a!=ev[col[x]].end()&&b!=ev[col[x]].end())renew(rt[dep[x]],rt[dep[x]],nl[lca(a->second,b->second)],1,1,n); if(a!=ev[col[x]].end())renew(rt[dep[x]],rt[dep[x]],nl[lca(x,a->second)],-1,1,n); if(b!=ev[col[x]].end())renew(rt[dep[x]],rt[dep[x]],nl[lca(x,b->second)],-1,1,n); } int last=0; for(int i=1;i<=n;i++)ev[i].clear(); for(int i=1;i<=m;i++) { int u=read()^last,v=read()^last; last=query(rt[min(dep[p[n]],dep[u]+v)],nl[u],nr[u]); printf("%d\n",last); } } return 0;}

我好菜啊都不会。

转载于:https://www.cnblogs.com/FallDream/p/bzojcontest2T2.html

转载地址:https://blog.csdn.net/weixin_30719711/article/details/98308285 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:sdut oj 2216 CIVIC DILL MIX
下一篇:day21-time与random等常用模块与包

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年03月27日 18时25分05秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

典型环节的matlab仿真分析,典型环节的MATLAB仿真.doc 2019-04-21
Php contenttype类型,各种类型文件的Content Type 2019-04-21
php使用redis持久化,redis如何持久化 2019-04-21
php7.1解压包安装,【Swoole】php7.1安装swoole扩展 2019-04-21
linux centos删除安装的包,CentOS yum认为已删除的软件包仍在安装中 2019-04-21
酒店管理系统c语言带注释,酒店管理系统--C语言版.pdf 2019-04-21
c语言 实现sizeof功能,C语言简单实现sizeof功能代码 2019-04-21
c语言sin函数近似值,用泰勒公式求sin(x)的近似值 2019-04-21
c 语言登录系统源代码,c语言源代码---------------个人图书管理系统 2019-04-21
android线程通信方式,Android 主线程和子线程通信问题 2019-04-21
cps1 cps2 android,图文教程:CPS1和CPS2模拟器使用 2019-04-21
在线设计 html5 表单,html5注册表单制作-表单制作-小程序表单制作 2019-04-21
android小闹钟课程设计,《小闹钟》教学设计 2019-04-21
mysql文件系统_MySQL文件系统先睹为快(1) 2019-04-21
nums在python_程序找到一对(i,j),其中nums [i] + nums [j] +(i -j)在Python中最大化?... 2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块 2019-04-21
grouping函数 mysql_sql聚合函数有哪些 2019-04-21
python os.walk如何不遍历隐藏文件_python 获取文件下所有文件或目录os.walk()的实例... 2019-04-21
python 股票估值_【中金固收·固收+】隐藏价值的角落:限售股AAP估值及Python实现方法(上)... 2019-04-21
java文档生成_Java文档自动生成 2019-04-21