Gym102536I Glory to Algotzka

Link
固定根节点和连通块大小，那么可行的黑点个数一定是一段区间。
然后树上背包求出这个区间即可，时间复杂度为(O(n^2+q))。

#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#define fi first
#define se second
using pi=std::pair<int,int>;
const int N=10007;
char str[N];int fa[N],size[N];pi f[N][N],g[N];std::vector<int>e[N];
int read(){int x;scanf("%d",&x);return x;}
void dfs(int u)
{
    size[u]=1,f[u][1].fi=f[u][1].se=str[u]=='C';
    for(int v:e[u])
    {
	dfs(v);
	for(int j=1;j<=size[v];++j) f[u][size[u]+j].fi=1e9;
	for(int j=size[u];j;--j) for(int k=size[v];k;--k) f[u][j+k].fi=std::min(f[u][j+k].fi,f[u][j].fi+f[v][k].fi),f[u][j+k].se=std::max(f[u][j+k].se,f[u][j].se+f[v][k].se);
	size[u]+=size[v];
    }
}
int main()
{
    int n=read(),q=read();
    for(int i=1;i<=n;++i) e[fa[i]=read()].push_back(i);
    scanf("%s",str+1),dfs(e[0][0]);
    for(int x,a,b;q;--q) x=read(),a=read(),b=read()+a,puts(b<=size[x]&&f[x][b].fi<=a&&a<=f[x][b].se? "COMPROMISED":"NOT COMPROMISED");
}