P2720

注意到颜色范围仅有

5\times 10^4

，这个数量级，所以我们可以考虑用 bitset 进行优化。

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

这里设

p

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

p_u=p_u\cup p_v,v\in son_u

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

CPP

#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;
}

文章操作

相关推荐

评论

P2720