codeforces 570D.Tree Requests

[题目大意]：

给定一棵树，树的每个节点对应一个小写字母字符，有m个询问，每次询问以vi为根节点的子树中，深度为hi的所有节点对应的字符能否组成一个回文串；

[题目分析]：

先画个图，可看出每次询问的所有节点都是一个从1开始bfs遍历完成的节点序列中的一段，已知深度hi的情况下，可以二分得到深度为hi的那一段的位置；

那么如何满足找到的节点必须在以vi为根的子树内这个条件？

可以想到dfs的时间戳，把1-n的数组按深度排序，深度相同的按照dfs时间戳排序；

这样就可以二分得到要求的所有节点的位置；

这样可以O（n）

分析回文串可知，如果奇数数量的字符不超过1个，那么一定能组成回文串；

用前缀和xor优化；

可以做到O(nlogn);

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<iomanip>

#include<map>

#include<set>

#include<vector>

#include<ctime>

#include<cmath>

using namespace std;

#define LL long long

#define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)

#define max(x,y) ((x)<(y)?(y):(x))

#define min(x,y) ((x)<(y)?(x):(y))

#define FILE "1"

#define pii pair<int,int>

const int maxn=,inf=;

int read(){

    int x=;bool flag=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')flag=;ch=getchar();}

    while(ch<=''&&ch>=''){x=x*+ch-'';ch=getchar();}

    return flag?-x:x;

}

struct node{

    int y,next;

}e[maxn<<];

int n,m;

int linkk[maxn],len=,sum[maxn];

int dfs_clock=,fa[maxn];

char s[maxn];

int f[maxn];

struct Node{

    int dep,pre,lat,id;

    bool operator<(const Node &b)const{return dep<b.dep||(dep==b.dep&&pre<b.pre);}

}a[maxn];

void insert(int x,int y){

    e[++len].y=y;

    e[len].next=linkk[x];

    linkk[x]=len;

}

void dfs(int x){

    a[x].pre=++dfs_clock;a[x].id=x;

    for(int i=linkk[x];i;i=e[i].next){

        if(e[i].y==fa[x])continue;

        a[e[i].y].dep=a[x].dep+;

        dfs(e[i].y);

    }

    a[x].lat=++dfs_clock;

}

void init(){

    n=read(),m=read();int x;

    up(i,,n){

        x=read();

        insert(i,x);

        insert(x,i);

        fa[i]=x;

    }

    scanf("%s",s+);

    a[].dep=;

    dfs();

    sort(a+,a+n+);

    for(int i=;i<=n;i++)f[a[i].id]=i;

}

int find(int x,int Dep){

    int left=,right=n,mid;

    int L=,R=;

    while(left<=right){

        mid=(left+right)>>;

        if(a[mid].dep<Dep)left=mid+;

        else {

            right=mid-;

            if(a[mid].dep==Dep)L=mid;

        }

    }

    left=,right=n,mid=;

    while(left<=right){

        mid=(left+right)>>;

        if(a[mid].dep<=Dep){

            left=mid+;

            if(a[mid].dep==Dep)R=mid;

        }

        else right=mid-;

    }

    if(!L&&!R)return ;

    left=L,right=R;

    int u=,v=;

    while(left<=right){

        mid=(left+right)>>;

        if(a[mid].pre>=a[f[x]].pre){

            right=mid-;

            if(a[mid].pre>=a[f[x]].pre&&a[mid].pre<=a[f[x]].lat)u=mid;

        }

        else left=mid+;

    }

    left=L,right=R;

    while(left<=right){

        mid=(left+right)>>;

        if(a[mid].pre<=a[f[x]].lat){

            left=mid+;

            if(a[mid].pre>=a[f[x]].pre&&a[mid].pre<=a[f[x]].lat)v=mid;

        }

        else right=mid-;

    }

    if(!u||!v)return ;

    int p=sum[v]^sum[u-];

    int cnt=;

    while(p){

        if(p&)cnt++;

        p>>=;

    }

    if(cnt>=)return ;

    else return ;

}

void work(){

    int x,y;

    for(int i=;i<=n;i++)sum[i]=sum[i-]^(<<(s[a[i].id]-'a'));

    while(m--){

        x=read(),y=read();

        if(find(x,y))printf("Yes\n");

        else printf("No\n");

    }

}

int main(){

    init();

    work();

    return ;

}

巴特西

codeforces 570D.Tree Requests

最新文章

热门文章