题解 | #小红的树#

开始时考虑的是暴力解法。
构建树的过程就不说了。这里有一点需要注意，题目中的树并非二叉树，只是一个无环连通图，所以树节点中只能设定保存父节点的指针。
在每次统计节点x的子节点中红色节点的个数时，使用一个辅助队列，开始时将x结点入队。进入循环后，查看队头结点是否为红色，然后遍历整棵树的所有结点，当遇到父节点指向队头结点的结点时，将其入队，重复以上过程，直到队空。
这种遍历思想是层序遍历的遍历思想，既然无法通过子节点来深度优先遍历，那么就用层序遍历的方法实现遍历统计。这样做确实没有用到动态规划的思想，寻找红色结点的时间复杂度为O(q*n^2)，在第4个用例(共6个)处超时。看来要AC必须考虑使用动态规划来降低时间复杂度。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct TreeNode{
    TreeNode* parent;
    bool isRed;
};

int main(){
    int n;
    cin >> n;
    vector<TreeNode> arr(n);
    for(int i = 1;i < n;i++){
        int parent;
        cin >> parent;
        arr.at(i).parent = &arr.at(parent - 1);
    }
    string str;
    cin >> str;
    for(int i = 0;i < n;i++){
        if(str[i] == 'R'){
            arr.at(i).isRed = true;
        }
    }
    int q;
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        x--;
        int count = 0;
        queue<TreeNode*> que;
        que.push(&arr.at(x));
        while(!que.empty()){
            TreeNode* now = que.front();
            que.pop();
            if(now->isRed){
                count++;
            }
            for(int i = 0;i < n;i++){
                if(arr.at(i).parent == now){
                    que.push(&arr.at(i));
                }
            }
        }
        cout << count << endl;
    }
}

动态规划的思想也比较简单。
选择使用邻接表来存储树结构，便于dfs。创建一个一维dp[i]数组来储存以i为头结点的子树中红色结点的个数。通过dfs遍历一次全树，即可将dp数组求出，然后根据输入的x返回对应的dp[x]即可。

这里其实遇到了比较有意思的事。
最开始用动态规划写完后，到第三个用例就超时了。甚至还不如上面暴力的方法。为了解决这一问题，参考了各位ac大佬的代码，发现逻辑上没有差异。那就只能扣细节了，先将邻接表二维数组table的定义方式改变，改变后第三个用例可以ac，不过第四个用例仍然超时。然后发现大佬们在传涂色信息时用了引用传递，而我用的是值传递，抱着试一试的想法改为引用传递后，所有用例ac。具体的改变见下方代码。

vector<vector<int>> table(n);//改变前，第三个用例超时
vector<int> table[n];//改变后，第三个用例ac，第四个用例超时

int findRed(int i, string str, vector<int> table[], vector<int>& dp);//改变前，涂色信息字符串使用值传递，第四个用例超时
int findRed(int i, string& str, vector<int> table[], vector<int>& dp);//改变后，涂色信息改为用用传递，全部ac

关于第一个改动使运行速度提升的原因，在查阅vector相关资料后并没有直接的回答。我个人的理解是，vector本身是对数组的封装，其低层实现就是数组，为了保证动态性，执行效率肯定比数组低。第一种定义方式定义了一个二维动态数组，而第二种定义方式虽然定义的也是一个二维数组，但其一维是固定的，一维是动态的，其执行效率必然优于二维都是动态的数组。
关于第二个改动使运行速度提升的原因，我认为是比较显然的。函数在值传递时，为了保护原有数据不被改变，会先创建一个原数据的副本，用于在函数执行中调用，创建副本的操作是有一定开销的。而函数在引用传递时，仅将原数据的地址传入函数的上下文中，其开销远比创建副本来的小，效率固然有明显提升。但这样其实牺牲了数据的安全性，在实际项目中需要斟酌后进行选择。
在之后又测试了将邻接表定义方式改回二维动态数组，而传值用引用传递的情况，结果是在第三个用例处超时。说明动态数组的开销还是较大的，在算法题中还是尽量避免使用vector吧。

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

using namespace std;

int findRed(int i, string& str, vector<int> table[], vector<int>& dp){
    int count = str[i] == 'R';
    for(int j = 0;j < table[i].size();j++){
        count += findRed(table[i][j], str, table, dp);
    }
    return dp[i] = count;
}

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> table[n];
    vector<int> dp(n, 0);
    for(int i = 1;i < n;i++){
        int parent;
        cin >> parent;
        table[parent - 1].push_back(i);
    }
    string str;
    cin >> str;
    findRed(0, str, table, dp);
    int q;
    cin >> q;
    while(q--){
        int x;
        cin >> x;
        x--;
        cout << dp[x] << endl;
    }
}