题解 CF1676G()-其他

题解 CF1676G()

``dp``

``2``
``n``

``2~n``

``1``
``-1``

``0``

``dfs``
``dfs``

``vector``
``clear``

``````#include<cstdio>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
const int N=4e3+10;
int T,n,ans;
vector<int> v[N];
int a[N],co[N],b[N];
void dfs(int x,int f){
b[x]=co[x];
for(int i=0;i<v[x].size();i++){
if(v[x][i]!=x && v[x][i]!=f){
dfs(v[x][i],x);
b[x]+=b[v[x][i]];
}
}
if(!b[x]){
ans++;
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
ans=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++){
v[i].clear();
}
for(int i=2;i<=n;i++){
scanf("%d",&a[i]);
v[a[i]].push_back(i);
v[i].push_back(a[i]);
}
for(int i=1;i<=n;i++){
char c;
cin>>c;
if(c=='W'){
co[i]=1;
}else{
co[i]=-1;
}
}
dfs(1,0);
printf("%d\n",ans);
}
return 0;
}

``````
————————

``dp``

``2``
``n``

``2~n``

``1``
``-1``

``0``

``dfs``
``dfs``

``vector``
``clear``

``````#include<cstdio>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
const int N=4e3+10;
int T,n,ans;
vector<int> v[N];
int a[N],co[N],b[N];
void dfs(int x,int f){
b[x]=co[x];
for(int i=0;i<v[x].size();i++){
if(v[x][i]!=x && v[x][i]!=f){
dfs(v[x][i],x);
b[x]+=b[v[x][i]];
}
}
if(!b[x]){
ans++;
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
ans=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++){
v[i].clear();
}
for(int i=2;i<=n;i++){
scanf("%d",&a[i]);
v[a[i]].push_back(i);
v[i].push_back(a[i]);
}
for(int i=1;i<=n;i++){
char c;
cin>>c;
if(c=='W'){
co[i]=1;
}else{
co[i]=-1;
}
}
dfs(1,0);
printf("%d\n",ans);
}
return 0;
}

``````