P2720

a_sad_soul · 2025-02-21 15:46:54 · 题解

注意到颜色范围仅有 5\times 10^4，这个数量级，所以我们可以考虑用 bitset 进行优化。

我们设某个点的 bitset 表示子树内存在的点有哪几个。

这里设 p 为子树包含颜色的集合，容易得到一个处理的方程：

但是发现最后得到的整个 bitset 会炸空间。所以我们可以把深搜的返回值定为 bitset 就不会炸了。

#include<bits/stdc++.h>
using namespace std;
const int NN= 6e4+10;
const int N  = 1e5+10;
int n,m;
vector<int>e[N];
bool vis[N];
int ans[N];
int col[N];
bitset<NN>dfs(int u){
    vis[u]=1;
    bitset<NN>ret;ret[col[u]]=1;
    for(int v:e[u])ret|=dfs(v);
    ans[u]=ret.count();
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;++i){
        int x;
        scanf("%d",&x);
        e[x].push_back(i);
    }
    for(int i=1;i<=n;++i)scanf("%d",&col[i]);
    dfs(1);
    scanf("%d",&m);
    while(m--){
        int q;
        scanf("%d",&q);
        printf("%d\n",ans[q]);
    }
    return 0;
}