Description

给一棵树，无修改操作，每次查询给出 (l,r)，查询 l 的子树在深度为 r 的节点对应的字母能不能构成回文串。

Solution

思路：dsu on tree(树上启发式合并)
算法的本质其实就是一个优化暴力的过程。按暴力的想法去统计，每次统计所有子树，再删除贡献，时间复杂度是 的。但是在dsu on tree的思想中，我们先进行轻重链剖分，只暴力统计并删除轻儿子，对于重儿子只统计不删除，有效地优化了暴力过程，能将时间复杂度降为
具体的算法步骤是：
1.暴力统计每个轻儿子(注意，每个轻儿子统计完后要删掉贡献）
2.统计重儿子
3.再重新暴力统计轻儿子，与重儿子的贡献合并提供给根节点
4.删除轻儿子的贡献。
在这题中需要得到回文串，关键条件在于出现奇数次的字母不能超过一个及以上，否则构不成回文串。令 表示深度为 u 时，字母i的出现次数，离线查询即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
vector<int> G[N];
vector<pair<int, int> > V[N];
int son[N], sz[N], dep[N], s1[N], ans[N];
int cnt[N][30], Son;
void dfs1(int u, int par) { // 第一遍dfs, 轻重链剖分
  sz[u] = 1;
  int maxz = 0;
  for(auto &x : G[u]) {
    if(x == par) continue;
    dep[x] = dep[u] + 1;
    dfs1(x, u);
    sz[u] += sz[x];
    if(sz[x] > maxz) { // 找重儿子
      maxz = sz[x];
      son[u] = x;
    }
  }
}
void update(int u, int val) { // 进行修改
  cnt[dep[u]][s1[u]] += val;
  for(auto &x : G[u]) {
    if(x != Son) { // 不是重儿子的都统计下来
      update(x, val);
    }
  }
}
void dsu(int u, int f) {
  for(auto &x : G[u]) { // 先统计轻儿子
    if(x == son[u]) continue;
    dsu(x, 0);
  }
  if(son[u]) { // 统计重儿子
    dsu(son[u], 1);
    Son = son[u];
  }
  update(u, 1);
  for(auto &x : V[u]) { // 对于当前点u的每个相关查询进行统计
    int tmp = 0, flag = 0;
    for(int j = 1; j <= 26; j++) {
      if(cnt[x.first][j] & 1) { // 统计奇数个的字母
        tmp++;
      }
      if(tmp >= 2) { // 奇数超过俩就不行
        ans[x.second] = 0;
        flag = 1;
      }
    }
    if(!flag) { 
      ans[x.second] = 1;
    }
  }
  if(son[u]) Son = 0;
  if(!f) update(u, -1); // 消除贡献
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, m; cin >> n >> m;
  for(int i = 2; i <= n; i++) {
    int x; cin >> x;
    G[x].push_back(i);
  }
  dep[1] = 1;
  string s;
  cin >> s; s = ' ' + s;
  for(int i = 1; i <= n; i++) {
    s1[i] = s[i] - 'a' + 1;
  }
  dfs1(1, 0);
  for(int i = 1; i <= m; i++) {
    int x, h; cin >> x >> h;
    V[x].push_back(make_pair(h, i));
  }
  dsu(1, 1);
  for(int i = 1; i <= m; i++) {
    string output = ans[i] ? "Yes\n" : "No\n";
    cout << output;
  }
  return 0;
}