题解 | 小红的树

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

#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;
    }
}