1 solutions

  • 0
    @ 2025-3-9 21:15:50
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll INF = 0x3f3f3f3f3f3f3f3f;
    typedef multiset<ll>::iterator itt;
    const int N = 5e5+11, P = 998244353;
    
    int n;
    char c[N];
    ll f[N], ans, cnt[N];
    int tot, head[N], ver[N], nex[N];
    
    void add(int x, int y){
    	nex[++tot] = head[x];
    	head[x] = tot;
    	ver[tot] = y;
    }
    
    void dfs(int x, int fa){
    //	cnt[x] += (c[x] == 'B' ? 1 : c[x] == 'W' ? -1 : 0);
    	for(int i=head[x]; i; i=nex[i]) if(ver[i] != fa){
    		int y = ver[i];
    		dfs(y, x);
    		cnt[x] += cnt[y];
    	} // if(cnt[x] == 0) printf("x=%d\n",x), ans ++;
    	ans += (!cnt[x]);
    }
    
    void work(){
    	scanf("%d",&n); ans = tot = 0;
    	for(int i=0;i<=n;i++) cnt[i] = c[i] = head[i] = 0;
    	for(int x,i=2;i<=n;i++) scanf("%d",&x), add(x, i), add(i, x);
    	
    	scanf("%s",c + 1); 
    	for(int i=1;i<=n;i++) cnt[i] = (c[i] == 'B' ? 1 : -1);
    	dfs(1, 0); printf("%lld\n",ans);
    }
    
    int main(){
    	int t = 1; scanf("%d",&t);
    	while(t--) work(); return 0;
    }
    
    
    • 1

    Information

    ID
    532
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    2
    Accepted
    1
    Uploaded By