https://community.topcoder.com/stat?c=problem_statement&pm=13185
被wck屠了。
考试时候想分类讨论，结果发现情况有点复杂，最后还是没调出来。
回去看了看题解，发现好像是树形DP，状态记得很巧妙。
假设当前红点在$x$，从$fa$来，容易知道此时$fa$是空的。
容易知道以$fa$为根的子树（即如图的绿色圈）中的黑点是可以任意移动的。
因为$fa$是空的，所以我们可以先把红点从$x$移到$fa$，然后将以$x$为子树中的所以黑点任意移动，最后再把红点从$fa$移到$x$。
所以以$x$为根的子树（即如图的蓝色圈）中的黑点也是可以任意移动的。
所以我们只需要知道以$x$为根的子树中的黑点的个数即可。
记$vis[x][fa][c]$表示当前红点在$x$，从$fa$来，且以$x$为根的子树中的黑点的个数为$c$的状态，$1$表示可以到达这种状态，$0$表示不可以到达这种状态。
然后DP即可。
#include<cstdio> #include<cstdlib> #include<iostream> #include<fstream> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<queue> #include<stack> #include<map> #include<utility> #include<set> #include<bitset> #include<vector> #include<functional> #include<deque> #include<cctype> #include<climits> #include<complex> //#include<bits/stdc++.h>适用于CF,UOJ，但不适用于poj using namespace std; typedef long long LL; typedef double DB; typedef pair<int,int> PII; typedef complex<DB> CP; #define mmst(a,v) memset(a,v,sizeof(a)) #define mmcy(a,b) memcpy(a,b,sizeof(a)) #define fill(a,l,r,v) fill(a+l,a+r+1,v) #define re(i,a,b) for(i=(a);i<=(b);i++) #define red(i,a,b) for(i=(a);i>=(b);i--) #define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++) #define fi first #define se second #define m_p(a,b) make_pair(a,b) #define p_b(a) push_back(a) #define SF scanf #define PF printf #define two(k) (1<<(k)) template<class T>inline T sqr(T x){return x*x;} template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;} template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;} inline int sgn(DB x){if(abs(x)<1e-9)return 0;return(x>0)?1:-1;} const DB Pi=acos(-1.0); int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; } const int maxn=300; int n; int d[maxn+10],g[maxn+10][maxn+10]; int mark[maxn+10]; int sz[maxn+10][maxn+10];//sz[i][j]表示i的父亲为j时，子树i的大小 int bl[maxn+10]; int res[maxn+10]; void addedge(int u,int v){g[u][++d[u]]=v;} int calsz(int x,int fa) { int &res=sz[x][fa],j; if(res)return res; res=1; re(j,1,d[x])if(g[x][j]!=fa)res+=calsz(g[x][j],x); return res; } int calbl(int x,int fa) { int &res=bl[x],j; res=mark[x]; re(j,1,d[x])if(g[x][j]!=fa)res+=calbl(g[x][j],x); return res; } queue<int>Q; int vis[maxn+10][maxn+10][maxn+10]; void push(int x,int fa,int c) { if(vis[x][fa][c])return; vis[x][fa][c]=1; Q.push((x<<20)|(fa<<10)|c); } int main() { freopen("puzzle.in","r",stdin); freopen("puzzle.out","w",stdout); int i,j; n=gint(); re(i,1,n){int fa=gint()+1;if(fa)addedge(fa,i),addedge(i,fa);} re(i,1,n)re(j,1,d[i])calsz(i,g[i][j]); re(i,1,n)mark[i]=gint();mark[1]=0; calbl(1,-1); int total=bl[1]; re(j,1,d[1]) { int v=g[1][j]; if(sz[v][1]>bl[v])push(v,1,bl[v]); } res[1]=1; while(!Q.empty()) { int status=Q.front(),x=status>>20,fa=(status>>10)&1023,c=status&1023;Q.pop();//当前红点在x，从fa来，子树内的黑点数为c res[x]=1; if(total-c<sz[fa][x])push(fa,x,total-c); int sc=0; re(j,1,d[x])if(g[x][j]!=fa)sc+=sz[g[x][j]][x]; re(j,1,d[x])if(g[x][j]!=fa) { int v=g[x][j]; for(int c2=0;c2<=c && c2<sz[v][x];c2++)if(c-c2<=sc-sz[v][x])push(v,x,c2); } } re(i,1,n)PF("%d ",res[i]);PF(" "); return 0; }