Moe's CF Life

喵哈~！各位算法爱好者们，大家好呀！咱是乃们的猫娘小助手，今天也要元气满满地和大家一起解决算法难题哦！这次我们要看的题目是 Codeforces 上的 "White-Black Balanced Subtrees"，一个关于树和染色的可爱问题，嘿嘿~ 🐾

题目大意喵

我们拿到了一棵有 n 个节点的有根树，树根是节点 1。每个节点都被染成了白色（'W'）或者黑色（'B'）。

题目问的是，在这棵树里，有多少个子树是“平衡”的？

那什么是“平衡”的子树呢？很简单喵，就是一个子树里，白色节点的数量和黑色节点的数量正好相等。

输入会告诉我们树的结构（通过一个父节点数组 a）和每个节点的颜色（通过一个字符串 s）。我们的任务就是数出所有平衡子树的数量。

举个栗子🌰，题目里的图：

      1(W)
     /  \
    2(B) 3(B)
   /    /  \
  4(W) 5(W) 6(W)
       |
       7(B)

对于以节点 3 为根的子树，它包含的节点有 {3, 5, 6, 7}。它们的颜色分别是 {B, W, W, B}。数一下，有两个白色节点和两个黑色节点，数量相等！所以，节点 3 的子树就是一个平衡子树，喵~。

解题思路与方法

看到“树”、“子树”、“统计信息”这些关键词，我们的猫猫雷达就应该“嘀嘀嘀”地响起来啦！这通常意味着我们可以用深度优先搜索 (DFS) 来解决问题，喵~。

为什么是 DFS 呢？因为一个节点 u 的子树信息，可以由它所有孩子节点的子树信息，再加上节点 u 自身的信息，组合而成。这天然就形成了一种递归的结构！

我们的思路就像一只好奇的小猫在探索一棵大树。从树根（节点 1）出发，沿着树枝往下爬。我们想知道以当前节点 u 为根的子树是不是平衡的，就需要知道这棵子树里总共有多少个白色节点和黑色节点。

这个信息怎么来呢？

首先，我们看看节点 u 自己是什么颜色，给自己先记上一笔。
然后，我们去问 u 的每一个孩子节点 v：“嘿，小家伙，你的子树里有多少白色和黑色的节点呀？”
孩子节点 v 也会用同样的方式去问它的孩子们，直到最底层的叶子节点。叶子节点最简单啦，它的子树只有它自己，所以它会直接告诉它的父亲：“我这里有1个xx色节点，0个另一种颜色的节点哦~”。
当一个节点 u 问完了它所有的孩子，并且拿到了它们的报告后，它就把所有孩子子树的白色/黑色节点数加起来，再加上自己本身的颜色。这样，u 就得到了自己整个子树的白色/黑色节点总数啦！
在得到总数之后，u 就可以判断自己的子树是不是平衡的了。如果是，我们的答案计数器就 +1。
最后，u 把自己算好的总数报告给它的父节点。

这个过程，从叶子节点开始，一层一层向上报告信息，直到根节点，其实就是一种后序遍历。DFS 的递归特性可以非常优美地实现这个过程。

所以，我们的 DFS 函数需要做两件事：

计算：计算并返回以当前节点为根的子树中，白色和黑色节点的数量。
更新答案：在计算完毕后，检查是否平衡，如果是，就更新全局的答案计数器。

代码详解喵

让我们来看看可爱的 C++ 代码是怎么实现这个想法的吧！

cpp

#include <iostream>
#include <vector>
#include <string>
#include <utility>

// 这是一个递归的 DFS 函数喵~
// 它会返回一个 pair {白色节点数, 黑色节点数}
// 同时，它会通过引用来更新我们的最终答案 ans
std::pair<int, int> dfs(int u, const std::vector<std::vector<int>>& adj, const std::string& s, int& ans) {
    // 1. 初始化当前节点 u 的颜色计数
    int white_count = (s[u - 1] == 'W');
    int black_count = (s[u - 1] == 'B');

    // 2. 递归地访问所有孩子节点 v，并累加它们的计数
    for (int v : adj[u]) {
        std::pair<int, int> child_counts = dfs(v, adj, s, ans);
        white_count += child_counts.first;
        black_count += child_counts.second;
    }

    // 3. 检查以 u 为根的子树是否平衡
    if (white_count == black_count) {
        ans++;
    }

    // 4. 返回当前子树的总计数给父节点
    return {white_count, black_count};
}

void solve() {
    int n;
    std::cin >> n;
    
    // 用邻接表来存树的结构，adj[p] 存的是 p 的所有孩子节点
    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 2; i <= n; ++i) {
        int p;
        std::cin >> p;
        adj[p].push_back(i);
    }
    
    std::string s;
    std::cin >> s;

    int ans = 0;
    // 从树根（节点1）开始我们的探索之旅！
    dfs(1, adj, s, ans);
    
    std::cout << ans << "\n";
}

int main() {
    // 一些加速输入输出的小魔法~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

代码分析：

solve() 函数：负责处理每个测试用例。它先读取 n，然后用一个 vector<vector<int>> adj 来构建树的邻接表。adj[p].push_back(i) 的意思是节点 i 的父节点是 p，所以 i 是 p 的一个孩子。读完颜色字符串 s 后，就初始化答案 ans = 0，然后调用 dfs(1, ...) 从根节点开始搜索。
dfs(u, adj, s, ans) 函数：这是我们解法的核心，喵~
- int white_count = (s[u - 1] == 'W');：这里用了一个小技巧，布尔值 true 在 C++ 中可以隐式转换为整数 1，false 转换为 0。所以如果 s[u-1] 是 'W'，white_count 就是 1，否则是 0。s 的索引是从 0 开始的，而节点编号是从 1 开始的，所以要用 u-1 哦。
- for (int v : adj[u]) { ... }：这个循环遍历了当前节点 u 的所有孩子 v。
- std::pair<int, int> child_counts = dfs(v, adj, s, ans);：这就是递归调用！我们去探索孩子 v 的子树。函数返回一个 pair，包含了 v 子树中白色和黑色的节点数。
- white_count += child_counts.first;：把从孩子那里得到的信息累加到当前节点 u 的计数器上。
- if (white_count == black_count) { ans++; }：在 u 的所有孩子都被访问过，并且它们的计数都被累加上来之后，white_count 和 black_count 就代表了整个以 u 为根的子树的最终统计。这时我们就可以进行判断了！如果相等，就找到了一个平衡子树，ans 增加！
- return {white_count, black_count};：最后，把为节点 u 计算出的结果返回给它的父亲，让父亲也能完成它的计算。

整个过程就像多米诺骨牌一样，从叶子节点开始，信息逐级向上传递，最终完成整个树的统计，是不是很优雅呢喵？

题目大意喵 ​

解题思路与方法 ​

代码详解喵 ​

代码分析： ​

相关知识点介绍 ​

题目大意喵

解题思路与方法

代码详解喵

代码分析：

相关知识点介绍