神仙美难题！让我来一步步感受这道题的魅力吧。
首先这个操作有点丑陋了，非常的难以刻画，我们要有转化条件的思想，让条件变得更为优美，我们发现这些操作其实就是我们要提出一棵虚树，满足相邻点颜色不同，求最大价值。
我们不难设计 \(f(u,i,0/1)\) 表示 \(u\) 子树内重量总和不超过 \(i\) 且暂时没有父亲边的点颜色都是 \(0/1\) 的最大价值。
我们需要背包合并，发现这样复杂度一定劣于 \(\mathcal{O}(M^2)\)，我们难以接受这样的复杂度。而因为这个问题不弱于背包问题，遂考虑单点插入，这一步是平凡的，因为我们必须走这一步。
而后面就变魔术了。不能背包合并似乎意味着子树 dp 的结构无法派上用场。如果我们要从上往下填则需要记录从根道当前位置所有祖先的信息，也不大好做，还要对每个点处理答案就更加麻烦了。
而做出这道题的关键步骤是利用 \((\max,+)\) 卷积的交换律。我们考虑优化刚刚的子树 dp，我们观察其转移方程，同时将状态改为 \(f(u,0/1,i)\)，就是交换了后两维。那么转移形如
而我们为了规避 \((\max,+)\) 卷积，我们在 \(v\) 转移 \(f(u,c)\) 时考虑带着 \(f(u,c)\) 的信息去递归进入 \(v\) 子树，并钦定我们选的顶上的点颜色为 \(c\)，我们发现这样是可以转移的，可以参考以下伪代码理解：
function dfs(c, dp)Dp[0] <- dpDp[1] <- dpfor d in {children of c} doDp[0] <- dfs(d, Dp[0])[0]Dp[1] <- dfs(d, Dp[1])[1]end forfor i = 0 to X - W[c] dochmax(Dp[C[c]][i + W[c]], Dp[C[c] ^ 1][i] + B[c])end forreturn Dp
可惜这样的算法是指数级别的，这堪称本题最难一步，因为在你不知道这能优化之前，你很难想出这种做法。
指数级的程序似乎完全无法优化，但是偏偏就有树链剖分这种东西。它有一个经典的性质，虽然感觉上轻边很多，但是一个点到祖先的轻边却只有 \(\log\) 条，这个就非常强大了，不过这只是一个预习，它结合主定理之后的力量更加超乎想象。
我们发现这个过程有个性质，就是你在第一个儿子进行转移时，你发现两种转移传进去的 dp 数组是同一个，也就是说我们可以有一个儿子只遍历一次，显然我们肯定会选择重儿子作为这一个儿子。而正是这一步，我们的做法复杂度直接就对了。
我们来证一下。设 \(y_1\ge y_2\ge \cdots,x-1=\sum y_i\)，则 \(T(x)=T(y_1)+2(T(y_2)+T(y_3)+\cdots)+\mathcal{O}(M)\)，考虑什么时候会取到 \(\max\)。对于 \(T\) 我们显然可以断言它是一个凸函数，如果它是多项式，那最高项一定大于 \(1\)。于是对于任意局面我们可以调整成形似 \(y_1=\cdots=y_k=\frac {x-1}{k}\) 这种状物，那么此时 \(T(x)=(2k-1)T(\frac{x-1}{k})+\mathcal{O}(M)\)，我们想要 \(\log_{k}(2k-1)\) 最大。我们可以证明它是凸函数，证明可以考虑先证 \(\log_{x}(2x)=\log_x 2+1\) 是凸的，然后函数中减 \(1\) 在这种情况下不影响凸性。又因为 \(k\) 是整数，所以 \(k=2\) 时函数取到最大值，于是 \(T(x)=3T(\frac {x-1} 2)+\mathcal{O}(M)\)，则 \(T(n)=\mathcal{O}(n^{\log_2 3}M)\)。
于是我们便会处理单次了。但是这样的做法无法计算全局的答案。因为我们很多时候计算的是初值 dp 数组受到影响的情况。不过我们在跑 dp 过程的时候发现重链的答案都是处理了的，那么我们直接对每一条重链处理一次就好了，具体实现可以看代码。这样做的复杂度用类似刚刚的分析可以分析出复杂度不变。
代码。这道题主要就是找到了一种好的方式去转移，然后用树链剖分去优化，其实也算是一种启发式合并，继承重儿子的答案，树剖在 dp 中的应用也是比较比较广泛的，这道题展示了树链剖分的伟大力量，而我个人认为主定理对于理解这道题也是必不可少的，他说明了重链剖分能优化这种 dp 甚至是递归搜索的本质，同时也非常精彩，并不是无聊干涩的东西。