【算法】树型DP

【题意】给定含n个点的树的形态，和n个数字Xv，要求给每个点赋予黑色或白色和权值，满足对于每个点v，子树v中和v同色的点的权值和等于Xv。n<=10^5

【题解】首先每个点的权值可以任意大，那么v的子树（不含v的部分）权值多少就无所谓了（因为缺的可以由v来补足），但是太大的话超过Xv就不可行了。

也就是说对于一个点v，假定其为黑色，那么子树中黑色总和为Xv，白色总和就要最小（从而后面加起来超过的可能更小），将白色总和定义为f[v]。

那么点v选择为黑色后，假设子树黑色总和为B（不含v），白色总和为W（f[v]），对于每个v的子节点u，有如下二选一：

B+=Xu，W+=f[u]。

B+=f[u]，W+=Xu。

然后做形如背包的操作就可以O(kXv)的计算每个点的f[v]。

树型DP即可。

#include
#include
#include
#include
using namespace std;
const int maxM=,maxn=,inf=0x3f3f3f3f;
int f[maxn],g[][maxM],n,first[maxn],tot,v[maxn];
struct edge{int v,from;}e[maxn];

int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
int min(int a,int b){return a=)g[X][j]=min(g[X][j],g[-X][j-v[y]]+f[y]);
if(j-f[y]>=)g[X][j]=min(g[X][j],g[-X][j-f[y]]+v[y]);
}
}
for(int i=;i<=v[x];i++)f[x]=min(f[x],g[X][i]);
}

int main(){
n=read();
for(int i=;i<=n;i++){
int p=read();
insert(p,i);
}
for(int i=;i<=n;i++)v[i]=read();
memset(f,0x3f,sizeof(f));
dfs();
if(f[]<inf)printf("POSSIBLE");else printf("IMPOSSIBLE");
return ;
}