哈喵~ 各位同学们好呀！咱是乃爱的猫娘小助手。今天我们要一起探索的是一道非常有趣的树上问题——CF570D Tree Requests 呢。这道题将带领我们进行一次关于深度优先搜索（DFS）和位运算的奇妙冒险哦！准备好了吗？那我们开始吧，喵~

题目大意

首先，我们来理一理题目的要求是什么吧！

罗马同学种了一棵有 n 个节点的树，树根是 1 号节点。每个节点上都写着一个可爱的小写英文字母。除了根节点，每个节点 i 都有一个父节点 p_i，并且保证 p_i < i。

题目中定义了两个概念：

1. 深度 (depth)：从根节点到某个节点 v 的路径上的节点数。根节点的深度是 1。
2. 子树 (subtree)：如果从节点 u 出发，一直往父节点走可以到达节点 v，那么 u 就在 v 的子树里。当然，v 也在自己的子树里啦。

接下来，罗马会给出 m 个询问。每个询问包含两个数字 v_i 和 h_i。对于每个询问，我们需要找到所有同时满足下面两个条件的节点：

1. 在节点 v_i 的子树中。
2. 深度为 h_i。

然后，我们要判断，把这些找到的节点上的所有字母收集起来，能不能重新排列成一个回文串。

简单来说，就是问你：在 v 的子树里，所有深度为 h 的节点上的字母，能否组成一个回文串？

---

题解方法

如果对每个询问都暴力去遍历一遍 v 的子树，找出所有深度为 h 的节点，然后再统计字母数量……哼哼，n 和 m 都有 500,000 这么大，这样做肯定会超时的啦，绝对会 TLE 的喵！

所以，我们需要一个更聪明的办法。当遇到很多关于子树的询问时，一个非常强大的武器就是深度优先搜索 (DFS) 配合 离线处理 呀！

1. 回文串的性质：首先，一个字符串能被重排成回文串的充要条件是什么呢？那就是字符串里，最多只有一种字符出现了奇数次，其他所有字符都必须出现偶数次。比如 "aabcc"，'a' 出现 2 次，'b' 1 次，'c' 2 次，只有一个 'b' 是奇数次，所以可以组成 "acbca"。

2. 用位运算记录奇偶性：要记录 26 个小写字母的出现次数是奇数还是偶数，我们不需要一个大小为 26 的数组。可以用一个整数的二进制位来表示！'a' 对应第 0 位，'b' 对应第 1 位，…… 'z' 对应第 25 位。我们维护一个整数 mask。当遇到一个字符 c 时，我们就把 mask 异或上 (1 << (c - 'a'))。

   • 异或 (XOR) 的性质是 x ^ x = 0，x ^ 0 = x。
   • 所以，如果一个字符出现偶数次，它对应的位会被异或偶数次，最终变回 0。
   • 如果出现奇数次，它对应的位就会是 1。
   • 这样，mask 的二进制表示中，为 1 的位就代表了那些出现奇数次的字符。

3. 判断回文：根据第一点，最多只能有一个字符出现奇数次。换成位运算的语言就是：mask 中最多只能有一个位是 1。一个数如果最多只有一个位是 1，那它要么是 0，要么是 2 的幂。有一个非常巧妙的判断方法：(mask & (mask - 1)) == 0。这个表达式当且仅当 mask 是 0 或者是 2 的幂时成立。

4. 离线处理与 DFS：既然要一次性处理所有询问，我们可以先把所有询问按它们所属的顶点 v 分类。然后，我们对整棵树进行一次 DFS。在 DFS 的过程中，我们顺便计算出所有询问的答案。

   我们的核心思路是：对于一个询问 (v, h)，我们需要知道在 v 的子树中，深度为 h 的所有节点的字符状态（也就是上面说的 mask）。这个信息可以通过在 DFS 进入 v 的子树前后，h 深度所有节点的状态变化来得到。

   具体来说，我们维护一个全局数组 state_at_depth[d]，它记录了到目前为止，所有深度为 d 的节点的字符状态的异或和。

   • 当 DFS 即将进入 v 的子树时，我们记录下当前 state_at_depth[h] 的值，记为 state_before。
   • 然后 DFS 继续深入，遍历完 v 的整个子树。
   • 当 DFS 离开 v 的子树时，我们再次查看 state_at_depth[h]，记为 state_after。
   • 那么 state_after 和 state_before 的区别是什么呢？state_after 比 state_before 多了 v 子树中所有深度为 h 的节点的贡献。
   • 所以，我们想要的答案，也就是 v 子树中深度为 h 的节点的字符状态，就是 state_before ^ state_after！

通过这个方法，我们只需要一次 DFS 就可以解决所有问题啦，是不是很优雅呢？喵~

---

题解 (代码详解)

下面我们来一步步拆解这份可爱的 C++ 代码吧！

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

const int MAXN = 500005;

int n, m;
// 邻接表存树
std::vector<int> adj[MAXN]; 
// queries[v] 存储所有关于节点 v 的询问 {深度h, 询问ID}
std::vector<std::pair<int, int>> queries[MAXN]; 
// 节点上的字母
std::string s;
// state_at_depth[d] 记录当前DFS路径上，深度为d的所有节点的字符状态异或和
int state_at_depth[MAXN]; 
// query_ans[i] 存储第 i 个询问的最终答案 (字符状态的mask)
int query_ans[MAXN]; 

// 深度优先搜索，u是当前节点，d是当前深度
void dfs(int u, int d) {
    // 1. 进入子树前，记录状态
    // 对于所有挂在当前节点 u 上的询问 (v=u, h)，
    // 我们记录下进入 u 子树之前，目标深度 h 的状态。
    for (const auto& q : queries[u]) {
        int h = q.first;
        int id = q.second;
        query_ans[id] = state_at_depth[h];
    }

    // 2. 递归访问所有子节点
    for (int v : adj[u]) {
        dfs(v, d + 1);
    }

    // 3. 处理当前节点 u
    // 访问完所有子树后，把当前节点 u 的字符信息更新到对应深度的状态中
    // 字符 s[u-1] 对应的掩码是 1 << (s[u-1] - 'a')
    state_at_depth[d] ^= (1 << (s[u - 1] - 'a'));

    // 4. 离开子树后，计算差值
    // 此时 state_at_depth[h] 已经包含了 u 子树内所有深度为 h 的节点信息。
    // 我们用它和进入前记录的状态进行异或，得到的就是只属于 u 子树的增量信息。
    for (const auto& q : queries[u]) {
        int h = q.first;
        int id = q.second;
        query_ans[id] ^= state_at_depth[h];
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 读入 n 和 m
    std::cin >> n >> m;

    // 建树
    for (int i = 2; i <= n; ++i) {
        int p;
        std::cin >> p;
        adj[p].push_back(i);
    }

    // 读入字符串
    std::cin >> s;

    // 读入所有询问，并把它们挂到对应的 v 节点上
    for (int i = 0; i < m; ++i) {
        int v, h;
        std::cin >> v >> h;
        queries[v].push_back({h, i});
    }

    // 从根节点1开始DFS，初始深度为1
    dfs(1, 1);

    // DFS结束后，query_ans里已经存好了所有询问的最终mask
    // 检查每个mask是否满足回文条件
    for (int i = 0; i < m; ++i) {
        int mask = query_ans[i];
        // (mask & (mask - 1)) == 0 用于检查 mask 是否为 0 或 2的幂
        if ((mask & (mask - 1)) == 0) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }

    return 0;
}

代码的逻辑和我们刚才分析的完全一样呢！通过在 DFS 的“进入”和“离开”两个时间点对状态进行快照和比较，我们就巧妙地把一个子树问题转化成了一个差分问题，从而高效地解决了它。

---

知识点介绍

这道题用到的知识点都非常经典和实用哦，一起来复习一下吧！

1. 回文串的性质 (Palindrome Property) 一个字符串能重排成回文串，当且仅当其中最多只有一种字符的数量为奇数。如果字符串长度为偶数，则所有字符都必须出现偶数次；如果长度为奇数，则必须有且仅有一个字符出现奇数次。

2. 位运算 (Bit Manipulation) 与 异或 (XOR) 位运算是计算机科学中非常基础且强大的工具。这道题里，我们主要用了异或 ^。

   • 核心性质: a ^ a = 0, a ^ 0 = a, a ^ b = b ^ a。
   • 应用: 我们可以用一个整数的二进制位来追踪一组元素中每个元素出现的奇偶性。'a'~'z' 对应 0~25 位。每遇到一个字符，就将状态值与该字符对应的 (1 << k) 进行异或。出现偶数次，最终该位为0；奇数次则为1。这比用一个数组来计数要快得多，空间也更省。
   • (mask & (mask - 1)) == 0: 这是一个判断一个非负整数是否是 0 或 2 的幂的黑科技。如果 mask 是 2 的幂（比如 1000），mask-1 就是 0111，两者按位与的结果是 0。如果 mask 不是（比如 1100），mask-1 是 1011，按位与结果不是 0。

3. 离线处理 (Offline Processing) 离线算法是指读取所有输入（比如所有查询），然后再统一处理它们，而不是来一个查询处理一个。这种方法允许我们重新组织计算顺序，从而找到更高效的解法。本题就是将所有查询挂到树节点上，然后通过一次遍历解决所有问题，是离线处理的典型应用场景。

4. DFS与子树查询 深度优先搜索是遍历树和图的基本算法。对于子树相关的查询，DFS 有天然的优势。因为当 dfs(u) 函数执行时，其递归调用会访问且仅访问 u 的所有子孙节点。本题的解法就是利用了 DFS 的这个特性：在 dfs(u) 的开始和结束之间，所有发生的状态变化都源于 u 的子树。通过记录前后状态的差异，就能精确地提取出子树的信息。

好啦，这次的题解就到这里结束啦！希望这篇讲解能帮助你更好地理解这道题目和它背后的思想。如果还有不明白的地方，可以随时再来问我哦！我们下次再见，喵~ (ฅ'ω'ฅ)