题解 | #小红的树#带缓存的递归vs循环法

题目的输入用的节点，目标是遍历节点，所以链表用邻接表（拉链表）存储

带缓存的递归

循环法

性能差别还蛮明显的

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int calc(const int& node, const vector<deque<int>> &children,vector<int>& dp,const string& colored){
    if(dp[node]>=0)return dp[node];
    dp[node]=0;
    if(colored[node]=='R') dp[node]++;
    for(int i=0;i<children[node].size();++i){
         dp[node]+=calc(children[node][i],children,dp,colored);
    }
    return dp[node];
}

int main() {
    int n,t,i,curNode,result;
    cin>>n;
    vector<int> dp(n,-1);
    vector<deque<int>> children(n,deque<int>());
    for(i=1;i<n;++i){
        cin>>t;
        t--;
        children[t].push_back(i);
    }
    string colored;
    cin>>colored>>t;//询问次数可扔掉。
    while(cin>>t){
        t--;//编号转下标
        cout<<calc(t,children,dp,colored)<<endl;
 
    }
 
}

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
 
int main() {
    int n,t,i,curNode,result;
    cin>>n;
    vector<int> dp(n,0);
    vector<int> parent(n);
    for(i=1;i<n;++i){
        cin>>t;
        parent[i]=t-1;
    }
    string colored;
    cin>>colored>>t;//询问次数可扔掉。
    parent[0]=-1;
    for(i=0;i<n;++i){
        if(colored[i]=='W')continue;
        t=i;
        while(t>=0){
            dp[t]++;
            t=parent[t];
        }
    }
 
    while(cin>>t){
        t--;//编号转下标
        cout<<dp[t]<<endl;
  
    }
}