Codeforces 570D - Tree Requests【树形转线性，前缀和】

时间：2022-03-23 00:38:22

http://codeforces.com/contest/570/problem/D

给一棵有根树（50w个点）（指定根是1号节点），每个点上有一个小写字母，然后有最多50w个询问，每个询问给出x和f，表示询问以x为根的子树，在第f层的所有节点上的字符能否组成一个回文串

首先树形转线性，把每个点按照DFS序重新标号，然后开个vector记下第i层都有哪些节点，

对于这一层的节点，维护一个前缀和，即某个字母出现过多少次，

这样对于某个询问x,f，我们能知道x为根的子树在线性数组中的序号范围，

然后二分查找第f层位于这个范围的点，通过前缀和就很容易求出来某个字母出现过多少次

因为回文串中最多有一个字母出现奇数次，所以就可以判断是否是回文串。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<set>

#include<map>

#include<stack>

#include<vector>

#include<queue>

#include<string>

#include<sstream>

#define eps 1e-9

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

#define rep(i,j,k) for(int i=j;i<=k;i++)

#define MAXN 500005

#define MAXM 40005

#define INF 0x3fffffff

#define PB push_back

#define MP make_pair

#define X first

#define Y second

#define clr(x,y) memset(x,y,sizeof(x));

using namespace std;

typedef long long LL;

int i,j,k,n,m,x,y,T,ans,big,cas,num,len;

bool flag;

vector<int> G[MAXN],D[MAXN];

int op[MAXN],ed[MAXN],lin[MAXN],d[MAXN],mxdp;

int ti[MAXN][];

char s[MAXN];

int p[];

void dfs(int u,int f)

{

    d[u]=f;

    mxdp=max(mxdp,f);

    lin[num]=u;//线性数组

    op[u]=num;//子树的起始位置

    D[f].PB(num); //D[f]表示f层都有哪些节点

    num++;

    for (int i=;i<G[u].size();i++)

    {

        int v=G[u][i];

        dfs(v,f+);

    }

    ed[u]=num-;//子树的终止位置

}

int main()

{

    scanf("%d%d",&n,&m);

    for (i=;i<=n;i++)

    {

        scanf("%d",&x);

        G[x].PB(i);

    }

    scanf("%s",s+);

    for (i=;i<=n;i++) D[i].PB();

    num=;

    dfs(,);

    for (i=;i<=mxdp;i++)

    {

        for (j=;j<D[i].size();j++)

        {

            int u=D[i][j-];

            int v=D[i][j];

            for (k=;k<;k++) ti[v][k]=ti[u][k];//ti[u][k]表示节点u所在的那一层，从开始到节点u，各个字母出现的次数

            ti[v][s[ lin[v]  ]-'a']++;

        }

    }

    for (i=;i<=m;i++)

    {

        int u,f;

        scanf("%d%d",&u,&f);

        int l=op[u],r=ed[u];

        int s=upper_bound(D[f].begin(),D[f].end(),l)-D[f].begin()-;

        int e=upper_bound(D[f].begin(),D[f].end(),r)-D[f].begin()-;

        if (s>=e)

        {

            printf("Yes\n");

        }else

        {

            int cnt=;

            e=D[f][e];

            s=D[f][s];

            for (k=;k<;k++)

                if ((ti[e][k]-ti[s][k]) % ) cnt++;

            if (cnt>) printf("No\n");

            else printf("Yes\n");

        }

    }

    return ;

}

相关文章