首页 > 代码库 > CF570D:Tree Requests
CF570D:Tree Requests
传送门
DFS重标号+二分
打比赛的时候想了很多方法..DFS序,BFS序,倍增什么的都考虑了一遍,但是几乎要么是可以维护两个区间但是代码复杂度爆炸,要么就是只能维护单一维度的信息。
这道题的具体做法就是先DFS遍历一遍,记一下每个点的出入栈时间。按照每个点的深度排序。这样就可以二分出深度,然后根据入栈的时间可以再在这个深度内二分出合适的区间。范围就是询问节点的出入栈时间。
//CF 570D//by Cydiater//2016.10.14#include <iostream>#include <cstdlib>#include <queue>#include <map>#include <ctime>#include <cmath>#include <map>#include <cstdio>#include <string>#include <cstring>#include <algorithm>using namespace std;#define ll long long#define up(i,j,n) for(int i=j;i<=n;i++)#define down(i,j,n) for(int i=j;i>=n;i--)const int MAXN=1e6+5;const int oo=0x3f3f3f3f;inline int read(){ char ch=getchar();int x=0,f=1; while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int LINK[MAXN],len=0,N,M,tim=0,pos[MAXN],Xor[MAXN],lef1,lef2,rig1,rig2;char s[MAXN];struct edge{ int y,next;}e[MAXN];struct Node{ int in,out,dep,id,v;}a[MAXN];namespace solution{ inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;} inline bool cmp(Node x,Node y){return x.dep==y.dep?x.in<y.in:x.dep<y.dep;} void dfs(int Node,int deep){ a[Node].in=++tim;a[Node].dep=deep;a[Node].id=Node; for(int i=LINK[Node];i;i=e[i].next)dfs(e[i].y,deep+1); a[Node].out=++tim; } void init(){ N=read();M=read(); up(i,2,N){ int Node=read(); if(i==Node)continue; insert(Node,i); } scanf("%s",s+1); up(i,1,N)a[i].v=s[i]-‘a‘; dfs(1,1); sort(a+1,a+N+1,cmp); up(i,1,N){ pos[a[i].id]=i; Xor[i]=((1<<a[i].v)^Xor[i-1]); } } int get1(int lim){//<= int leftt=1,rightt=N,mid; while(leftt+1<rightt){ mid=(leftt+rightt)>>1; if(a[mid].dep>=lim) rightt=mid; else leftt=mid; } if(a[leftt].dep>=lim) return leftt; return rightt; } int get2(int lim){//>= int leftt=1,rightt=N,mid; while(leftt+1<rightt){ mid=(leftt+rightt)>>1; if(a[mid].dep<=lim) leftt=mid; else rightt=mid; } if(a[rightt].dep<=lim) return rightt; return leftt; } int get3(int lim){//<= int leftt=lef1,rightt=rig1,mid; while(leftt+1<rightt){ mid=(leftt+rightt)>>1; if(a[mid].in>=lim) rightt=mid; else leftt=mid; } if(a[leftt].in>=lim) return leftt; return rightt; } int get4(int lim){//>= int leftt=lef1,rightt=rig1,mid; while(leftt+1<rightt){ mid=(leftt+rightt)>>1; if(a[mid].in<=lim) leftt=mid; else rightt=mid; } if(a[rightt].in<=lim) return rightt; return leftt; } void slove(){ while(M--){ int Node=pos[read()],dep=read(); if(a[Node].dep>=dep){puts("Yes");continue;} lef1=get1(dep);rig1=get2(dep); lef2=get3(a[Node].in+1);rig2=get4(a[Node].out-1); int S=Xor[rig2]^Xor[lef2-1];int flag=0; if(lef2>rig2){ puts("Yes"); continue; } up(i,0,25)if((S&(1<<i))==(1<<i)&&flag){ puts("No"); flag=-1; break; }else if((S&(1<<i))==(1<<i)) flag=1; if(flag!=-1)puts("Yes"); } }}int main(){ //freopen("input.in","r",stdin); using namespace solution; init(); slove(); return 0;}
CF570D:Tree Requests
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。