[DP记录]AT3536 [ARC083C] Bichrome Tree

**题意** ： 给出一棵 $n$ 个点的有根树，点 $u$ 有参数 $x_u$。 点可以染成黑白两色之一，且可以赋予一个自然数权值。 需要使得每个点 $u$ 的子树内（包括 $u$ 本身）与 $u$ 同色的点权和恰为 $x_u$。 判定是否存在一组符合要求的染色方案。 $n\leq 1000,x\leq 5000$ ，时限$\texttt{2s}$。 ------------ 先考虑最稳健的布尔 $\rm DP$。 记 $dp[u][c]$ 表示 $u$ 子树内与 $u$ 同色点权和为 $x_u$ ，异色点权和为 $c$ 的方案是否存在。 转移时，记 $(a,b)$ 表示同色权值和为 $a$ ，异色权值和为 $b$。 对于直接儿子 $v$ ， $dp[v][c]$ 可以贡献 $(x_v,c)$ 或者 $(c,x_v)$。 在每个儿子处选一个二元组，然后加起来，记为 $(a,b)$。 最后 $u$ 本身可以贡献任意的 $(0\sim \infty,0)$。故 $(a,b)$ 需要满足 $a\leq x_u$ 即可贡献。 由于合法约束形如 $a\leq x_u$ ，可以得到贪心策略 ： 对于同一颗子树，若 $dp[v][c_1]=dp[v][c_2]=1$ ，且 $c_1<c_2$ ，则选择 $c_1$。因为前者贡献的两个对子严格优于（更可能合法）后者贡献的两个。 于是，可以将状态改为 ： $dp[u]$ 表示 $u$ 子树内与 $u$ 同色的点权和为 $x_u$ ，异色点权和的最小值。 先在问题相当于 ： 给出若干个对子，可以选择翻转其中的一些，需要使得左侧权值和 $\leq x$ ，右侧权值和尽量小。 注意到两侧的和是固定的，故只需左侧的和尽量大。跑 `01` 背包即可。 利用 `bitset` ，复杂度可以做到 $O(nx/\omega)$。 ```cpp #include<cstdio> #include<vector> #include<bitset> #define MaxN 1050 #define MaxS 5050 using namespace std; vector<int> g[MaxN]; int n,dp[MaxN],x[MaxN]; bitset<MaxS> sav; void dfs(int u) { for (int i=0;i<g[u].size();i++) dfs(g[u][i]); sav.reset();sav[x[u]]=1; for (int i=0;i<g[u].size();i++){ int v=g[u][i]; sav=(sav>>x[v])|(sav>>dp[v]); dp[u]+=x[v]+dp[v]; }if (!sav.any()){puts("IMPOSSIBLE");exit(0);} dp[u]-=x[u]-sav._Find_first(); } int main() { scanf("%d",&n); for (int i=2,fa;i<=n;i++){ scanf("%d",&fa); g[fa].push_back(i); } for (int i=1;i<=n;i++)scanf("%d",&x[i]); dfs(1); printf("POSSIBLE"); return 0; } ```