小红的树

C 解法, 执行用时: 25ms, 内存消耗: 2564KB, 提交时间: 2021-11-15

#include <stdio.h>

int main(void)
{
    int n=0,q=0;
    int arr[100002];
    char str[100002];
    int d[100002];
    int i=0,j=0;
    int x=0;
    scanf("%d",&n);
    for(i=1;i<=n-1;i++)
    {
        scanf("%d",&arr[i]);
    }
    scanf("%s",str);
    scanf("%d",&q);
    for(i=1;i<=n;i++)
    {
        d[i]=(str[i-1]=='R')?(1):(0);
    }
    for(i=n-1;i>0;i--)
    {
        d[arr[i]]=d[arr[i]]+d[i+1];
    }
    for(i=0;i<q;i++)
    {
        scanf("%d",&x);
        printf("%d\n",d[x]);
    }
    return 0;
}

C++ 解法, 执行用时: 26ms, 内存消耗: 5112KB, 提交时间: 2021-12-15

#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &f) 
{
    f=0;T fu=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-'){fu=-1;}c=getchar();}
    while(c>='0'&&c<='9') {f=(f<<3)+(f<<1)+(c&15);c=getchar();}
    f*=fu;
}
template <typename T>
void print(T x) 
{
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+48);
    else print(x/10),putchar(x%10+48);
}
template <typename T>
void print(T x, char t) 
{
    print(x);putchar(t);
}
const int maxn=1e5+50;
int n,red[maxn],ans[maxn];
char s[maxn];
vector<int> vec[maxn];
int dfs(int root)
{
    for(auto x:vec[root])
    {
        ans[root]+=dfs(x);
    }
    return ans[root]=ans[root]+red[root];
}
void solve()
{
    read(n);
    for(int i=2;i<=n;++i)
    {
        int x;
        read(x);
        vec[x].push_back(i);
    }
    scanf("%s",s+1);
    for(int i=1;i<=n;++i)
    {
        if(s[i]=='R')
        red[i]=1;
    }
    dfs(1);
    int q;
    read(q);
    while(q--)
    {
        int x;
        read(x);
        print(ans[x],'\n');
    }
}
int main()
{
    #ifdef AC
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    clock_t program_start_clock=clock();
    solve();
    #ifdef NO_TLE
    fprintf(stderr,"\nTotal Time: %lf ms",double(clock()-program_start_clock)/(CLOCKS_PER_SEC/1000));
    #endif
    return 0;
}

C 解法, 执行用时: 27ms, 内存消耗: 2324KB, 提交时间: 2022-04-01

# include <stdio.h>
# include <string.h>
# include <limits.h>

int max(int a,int b){
    return a>b?a:b;
}
int main() {
    int mm= INT_MIN;
    int m;
    scanf("%d",&m);
    int fnode[m],num[m], dp[m];
    

    char str[m+1];
    int i,j,n,cnt;
    fnode[0]=1;
    for(i=1;i<m;i++){
        scanf("%d",fnode+i);
    }
    scanf("%s",str);
    int q;
    scanf("%d",&q);
    int qr[q];
    
    for(i=0;i<q;i++){
        scanf("%d",qr+i);
    }
    for(i=0;i<m;i++){
        if(str[i] == 'W') num[i]= 0;
        if(str[i] == 'R' ) num[i]=1;
    }
    cnt=0;
    for(i=0;i<m;i++){
        cnt += num[i];
        dp[i]=mm;
    }
    dp[0] = cnt;
    for(i=m-1;i>0;i--){
        j=i;
        dp[j] = max(dp[j],num[j]);
        n=fnode[i];
        
        if(n!=1){
            dp[n-1] =max(dp[n-1]+dp[j], num[n-1]+dp[j]);
            continue;
        }
    }
        for(i=0;i<q;i++){
        printf("%d\n",dp[qr[i]-1]);
    }    
    return 0;
}

C 解法, 执行用时: 28ms, 内存消耗: 2308KB, 提交时间: 2022-03-16

# include <stdio.h>
# include <string.h>
# include <limits.h>

int max(int a,int b){
	return a>b?a:b;
}
int main() {
	int mm= INT_MIN;
	int m;
	scanf("%d",&m);
	int fnode[m],num[m], dp[m];
	

	char str[m];
	int i,j,n,cnt; 
	fnode[0]=1;
	for(i=1;i<m;i++){
		scanf("%d",fnode+i);
	}
	scanf("%s",str);
	int q;
	scanf("%d",&q);
	int qr[q];
	
	for(i=0;i<q;i++){
		scanf("%d",qr+i);
	}
	for(i=0;i<m;i++){
		if(str[i] == 'W') num[i]= 0;
		if(str[i] == 'R' ) num[i]=1;
	}
	cnt=0;
	for(i=0;i<m;i++){
		cnt += num[i];
		dp[i]=0;
	}
	dp[0] = cnt;
	for(i=m-1;i>0;i--){
		j=i;
	
    	dp[j] = max(dp[j],num[j]);
		n=fnode[i];		
		if(n!=1){
			dp[n-1] =max(dp[n-1]+dp[j], num[n-1]+dp[j]);        
		}	
	}
		for(i=0;i<q;i++){
		printf("%d\n",dp[qr[i]-1]);
	}	
	return 0;
}

C 解法, 执行用时: 30ms, 内存消耗: 2424KB, 提交时间: 2022-04-07

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
# include <limits.h>

int main() {
    int mm = INT_MIN;
    int m;
    scanf("%d", &m);
    int fnode[m], num[m], dp[m];


    char str[m + 1];
    int i, j, n, cnt;
    fnode[0] = 1;
    for (i = 1; i < m; i++) {
        scanf("%d", fnode + i);
    }
    scanf("%s", str);
    int q;
    scanf("%d", &q);
    int qr[q];

    for (i = 0; i < q; i++) {
        scanf("%d", qr + i);
    }
    for (i = 0; i < m; i++) {
        if (str[i] == 'W') num[i] = 0;
        if (str[i] == 'R' ) num[i] = 1;
    }
    cnt = 0;
    for (i = 0; i < m; i++) {
        cnt += num[i];
        dp[i] = mm;
    }
    dp[0] = cnt;
    for (i = m - 1; i > 0; i--) {
        j = i;
        dp[j] = fmax(dp[j], num[j]);
        n = fnode[i];

        if (n != 1) {
            dp[n - 1] = fmax(dp[n - 1] + dp[j], num[n - 1] + dp[j]);
            continue;
        }

    }

    for (i = 0; i < q; i++) {
        printf("%d\n", dp[qr[i] - 1]);
    }

    return 0;
}

详情