dfs序专题 Tree Requests

Tree Requests

https://ac.nowcoder.com/acm/problem/111044

Tree Requests

题目地址:

https://ac.nowcoder.com/acm/problem/111044

基本思路:

有对每个子树下的查询,但没有修改,考虑 $dsu\ on\ tree$ ，
我们先将查询离线,并且预处理出深度,
对于每一棵子树我们统计一下每种深度下每个字母的出现次数,
由题意我们知道只要在某个深度下出现次数为奇数个的字母数量大于 $1$ 就不能组成回文。
这样我们就能得到这棵子树对应的每个深度下的查询结果,
然后保留重儿子的结果删除轻儿子的结果就行了。

参考代码:

#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define debug(x) cerr << #x << " = " << x << '\n';
#define pll pair <ll, ll>
#define fir first
#define sec second
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 5e5 + 10;
int n,m,dep[maxn],sz[maxn],son[maxn];
vector<int> G[maxn];
char s[maxn];
int mm[maxn][26],tmp;
vector<int> memo[maxn];
bool ans[maxn];
struct Q{
    int v,h,id;
}q[maxn];
signed main() {
  IO;
  cin >> n >> m;
  for (int i = 2; i <= n; i++) {
    int p;
    cin >> p;
    G[i].push_back(p);
    G[p].push_back(i);
  }
  cin >> (s + 1);
  for (int i = 1; i <= m; i++) {
    int v, h;
    cin >> v >> h;
    memo[v].push_back(i);
    q[i] = {v, h, i};
  }
  function<void(int, int, int)> dfs1 = [&](int u, int par, int d) {
      dep[u] = d, sz[u] = 1, son[u] = 0;
      for (auto to : G[u]) {
        if (to == par) continue;
        dfs1(to, u, d + 1);
        sz[u] += sz[to];
        if (sz[to] > sz[son[u]]) son[u] = to;
      }
  };
  dfs1(1, 0, 1);
  function<void(int, int, int)> add = [&](int u, int par, int val) {
      mm[dep[u]][s[u] - 'a'] += val;
      for (auto to : G[u]) {
        if (to == par || to == tmp) continue;
        add(to, u, val);
      }
  };
  function<void(int, int, int)> dfs2 = [&](int u, int par, int op) {
      for (auto to : G[u]) {
        if (to == par || to == son[u]) continue;
        dfs2(to, u, 0);
      }
      if (son[u]) dfs2(son[u], u, 1);
      tmp = son[u];
      add(u, par, 1);
      for (auto pos : memo[u]) {
        int h = q[pos].h;
        int odd = 0;
        for (int i = 0; i < 26; i++) if (mm[h][i] & 1) odd++;
        if (odd <= 1) ans[q[pos].id] = true;
      }
      tmp = 0;
      if (!op) add(u, par, -1);
  };
  dfs2(1, 0, 1);
  for (int i = 1; i <= m; i++) if (ans[i]) puts("Yes"); else puts("No");
  return 0;
}