CodeForces 570D Tree Requests

活动地址：CSDN21天学习挑战赛

题目描述

Roman planted a tree consisting of nn vertices. Each vertex contains a lowercase English letter. Vertex 11 is the root of the tree, each of the n-1n−1 remaining vertices has a parent in the tree. Vertex is connected with its parent by an edge. The parent of vertex ii is vertex p_{i}pi​ , the parent index is always less than the index of the vertex (i.e., p_{i}<i ).

The depth of the vertex is the number of nodes on the path from the root to vv along the edges. In particular, the depth of the root is equal to 11 .

We say that vertex uu is in the subtree of vertex vv , if we can get from uu to vv , moving from the vertex to the parent. In particular, vertex vv is in its subtree.

Roma gives you mm queries, the ii -th of which consists of two numbers v_{i}vi​ , h_{i}hi​ . Let's consider the vertices in the subtree v_{i}vi​ located at depth h_{i}hi​ . Determine whether you can use the letters written at these vertices to make a string that is a palindrome. The letters that are written in the vertexes, can be rearranged in any order to make a palindrome, but all letters should be used.

输入格式

The first line contains two integers nn , mm ( 1<=n,m<=5000001<=n,m<=500000 ) — the number of nodes in the tree and queries, respectively.

The following line contains n-1n−1 integers p_{2},p_{3},...,p_{n}p2​,p3​,...,pn​ — the parents of vertices from the second to the nn -th ( 1<=p_{i}&lt;i ).

The next line contains nn lowercase English letters, the ii -th of these letters is written on vertex ii .

Next mm lines describe the queries, the ii -th line contains two numbers v_{i}vi​ , h_{i}hi​ ( 1<=v_{i},h_{i}<=n1<=vi​,hi​<=n ) — the vertex and the depth that appear in the ii -th query.

输出格式

Print mm lines. In the ii -th line print "Yes" (without the quotes), if in the ii -th query you can make a palindrome from the letters written on the vertices, otherwise print "No" (without the quotes).

题意翻译

简化版:

给定一个以 1 为根的 n 个结点的树，每个点上有一个字母（a-z），每个点的深度定义为该节点到 1 号结点路径上的点数。每次询问 a,b 查询以 a 为根的子树内深度为 b 的结点上的字母重新排列之后是否能构成回文串

思路：

• 首先容易得出字母数量为奇数的不同字母的个数 <= 1 时，答案为 yes，否则为 no
• 因为存在一个字母为奇数时可以把多的那一个放中间
• 这个题有几个地方需要处理
• 因为题目所求为以a为根的子树中深度为b的这层结点上的字母，询问时会有询问同一个根的情况
• 同时为了方便存每次询问的答案
• 所以需要绑定根，深度，第几次询问这些信息，因为有同根的情况，所以还要存个二维来遍历对应
• 所以在这里使用vector数组存放结构体类型，结构体里包含深度和第几次询问这些信息
• 然后有了这些信息后，往树上套就行

• #include<bits/stdc++.h>
  using namespace std;
  const int N=1e6+10;
  typedef long long ll;
  int head[N],cnt;
  int siz[N],son[N];
  int col[N],cntt[N][26];
  int ans[N],deep[N];
  int flag,kmax,n,m,u;
  char sstring[N];
  struct stuu{
  	int to,nt;
  }ed[N*2];
  struct sty{
      int k,id;//id代表第几次询问 k代表深度
  };
  vector<sty> q[N];
  void add(int u,int v){//链式前向星加边
  	ed[cnt]=stuu{v,head[u]};
  	head[u]=cnt++;
  }
  void dfs1(int u,int f){//u为当前节点,f为当前节点的父节点；初始化1
      siz[u]=1;
      deep[u]=deep[f]+1;//深度+1
      int maxsize=-1;//判断是不是重儿子的临时变量
      for(int i=head[u];i!=-1;i=ed[i].nt){//遍历所有儿子，不断更新同时找到重儿子
  		int v=ed[i].to;
          if(v==f) continue;//是父亲肯定直接跳过
          dfs1(v,u);//深度遍历,当前节点变为父节点，找到的儿子变为当前节点继续遍历下去
          siz[u]+=siz[v];//遍历完成后，让当前节点的大小加上儿子的大小
          if(siz[v]>maxsize){//如果儿子的大小大于临时变量
              maxsize=siz[v];//就赋给临时变量
              son[u]=v;//更改当前节点的重儿子
          }
      }
  }
  void count(int u,int f,int val){//统计某节点及其所有轻儿子的贡献
      cntt[deep[u]][sstring[u]-'a']+=val;//val为正为负可以控制是增加贡献还是删除贡献 代表字符sstring[u]在第deep[u]层出现的次数
      for(int i=head[u];i!=-1;i=ed[i].nt){//排除被标记的重儿子，统计其它儿子子树信息
          int v=ed[i].to;
          if(v==f||v==flag) continue;
          count(v,u,val);
      }
  }
  bool findd(int se[]){//计算是否回文
      int r=0;
      for(int i=0;i<26;i++){
          if(se[i]%2) ++r;
          if(r>1) return 0;
      }
      if(r>1) return 0;
      return 1;
  }
  void dfs2(int u,int f,int keep){
      //遍历所有轻儿子及其子树算其答案删贡献
      for(int i=head[u];i!=-1;i=ed[i].nt){//遍历所有轻儿子
          int v=ed[i].to;
          if(v==f||v==son[u]) continue;//是父节点或重儿子就跳过
          dfs2(v,u,false);
      }
      //处理重儿子及其子树算其答案不删贡献
      if(son[u]){
          dfs2(son[u],u,true);
          flag=son[u];//标记重儿子，方便统计贡献时跳过
      }
      count(u,f,1);//暴力统计u及其所有轻儿子的贡献合并到刚算出的重儿子信息里
      flag=0;
      for(int i=0;i<q[u].size();i++){//遍历以u为根的询问
          ans[q[u][i].id]=findd(cntt[q[u][i].k]);//记录以u为根的答案
      }
      if(!keep) count(u,f,-1);//把需要删贡献的删掉
  }
  int main(){
      memset(head,-1,sizeof(head));
      cin>>n>>m;
      for(int i=2;i<=n;i++){
          scanf("%d",&u);
          add(u,i),add(i,u);
      }
      scanf("%s",sstring+1);
      dfs1(1,0);
      int a,b;
      for(int i=1;i<=m;i++){
          scanf("%d%d",&a,&b);
          q[a].push_back((sty){b,i});
      }
      dfs2(1,0,0);
      for(int i=1;i<=m;i++){
          puts(ans[i]?"Yes":"No");
      }
  }