小红的树

第一行一个正整数 $n$ ，代表树的节点个数。
第二行有 $n-1$ 个正整数，分别表示第 $2$ 个节点到第 $n$ 个节点每个节点的父亲。
接下来一个长度为 $n$ 的、由'W'或'R'字符组成的字符串。第 $i$ 个字符为'W'代表该字符没被染色，若字符为'R'代表该字符被染成了红色。
接下来一个正整数 $q$ ，代表小红的询问次数。

接下来的 $q$ 行，每行有一个正整数 $x$ ，代表一次询问。

$(1\leq n,q \leq 10^5,1 \leq x \leq n)$

C++ 解法, 执行用时: 216ms, 内存消耗: 2584K, 提交时间: 2021-10-31 22:14:50

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int fa[N];
int col[N];
int main()
{
    int i,n;
	cin>>n;
	for(i = 2;i<=n;i++) cin>>fa[i];
	for(i = 1;i<=n;i++) 
    {
		char ch;
		cin>>ch;
		col[i] = ch=='R'?1:0;
	} 
	for(i=n;i>=2;i--)
    {
		col[fa[i]]+=col[i];
	}
	int q;
	cin>>q;
	while(q--)
    {
		int k;
		cin>>k;
		cout<<col[k]<<endl;
	}
}

Python3 解法, 执行用时: 604ms, 内存消耗: 16632K, 提交时间: 2022-06-16 11:25:09

n =  int(input())
t = [0]+[int(x) for x in input().split()] #前面补一个0，方便后面的循环控制
c = input()

dp=[0 for x in range(n+1)]
for i in range(n-1,-1,-1):
    if c[i]=='R':
        dp[i+1] =dp[i+1] +1  #当前节点加1
    dp[t[i]] = dp[t[i]] +dp[i+1] #当前节点的父节点+当前节点 不是红色，也要把本节点的统计数传上去        

q = int(input())
for _ in range(q):
    x = int(input())
    print(dp[x])

详情