Tree Requests（dsu on tree）

题目：

给一棵树，每个点有一个英文字母。 $q$ 次询问 $(u，h)$ ，问子树 $u$ 内所有深度为 $h$ 的点里的字母能否重排成一个回文串。
$n，q≤5e5$

做法：

处理子树上的询问，不带修改，询问可离线，我们可以考虑用 $dsu\space on\space tree$ 。这是一种统计子树信息的方式，通过调整 $dfs$ 顺序，保留重儿子中的信息来优化复杂度。
在这个题里，我们要做的就是对每棵子树，得到 $cnt[h][x]$ 数组， $cnt[h][x]$ 代表这棵子树内深度为 $h$ 的点中，字符 $x$ 出现的次数。因为能否重排成回文串我们只需知道奇数字符的数量，设为 $odd$ ，若 $odd$ >1则 $NO$ ，否则 $YES$ 。所以这题其实是很裸的 $dsu$ ，我们每次处理出子树的 $cnt[h][x]$ 数组，然后就能判断完该子树下的所有询问。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 5e5 + 7;
char s[N];
vector<int> g[N];
vector<pair<int,int>> ask[N];
int dep[N], sze[N], son[N], skip;
int cnt[N][26], ans[N];
void dfs(int u){
    sze[u] = 1, son[u] = 0;
    for (auto &v : g[u]){
        dep[v] = dep[u]+1;
        dfs(v);
        sze[u] += sze[v];
        if (sze[son[u]] < sze[v]) son[u] = v;
    }
}
void cal(int u, int op){
    cnt[dep[u]][s[u]-'a'] += op;
    for (auto &v : g[u]) if (v != skip){
        cal(v, op);
    }
}
void dsu(int u, int keep){
    for (auto &v : g[u]) if (v != son[u]) dsu(v, 0);
    if (son[u]) dsu(son[u], 1), skip = son[u];
    cal(u, 1); skip = 0;
    for (auto &pr : ask[u]){
        int d = pr.first, id = pr.second;
        int even = 0, odd = 0;
        for (int i = 0; i < 26; ++i){
            (cnt[d][i]&1) ? odd++ : even++;
        }
        ans[id] = (odd > 1) ? 0 : 1;
    }
    if (!keep) cal(u, -1);
}
int main(void){
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; ++i){
        int x; scanf("%d", &x);
        g[x].push_back(i);
    }
    scanf("%s", s+1);
    for (int i = 1; i <= m; ++i){
        int u, d; scanf("%d%d", &u, &d);
        ask[u].push_back(make_pair(d, i));
    }
    dep[1] = 1;
    dfs(1);
    dsu(1, 0);
    for (int i = 1; i <= m; ++i) printf("%s\n", ans[i] ? "Yes" : "No");
    return 0;
}