1 solutions
-
0
#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