主要思路
首先发现两端并不会影响，所以可以直接做分段的线性 DP。正常思考暴力，发现每次都需要枚举颜色，非常麻烦。但是我们可以发现一个特别好的性质：每一次区间的颜色都取决于这个区间的最后一个元素，因为意识到选其他颜色时，我们大可把这个区间的右端点进行调整，使得下一个区间不会更劣。
首先发现两端并不会影响，所以可以直接做分段的线性 DP。正常思考暴力，发现每次都需要枚举颜色，非常麻烦。但是我们可以发现一个特别好的性质：每一次区间的颜色都取决于这个区间的最后一个元素，因为意识到选其他颜色时，我们大可把这个区间的右端点进行调整，使得下一个区间不会更劣。
这道题直接去想性质不好想，因为贪心的话、找到两个大小相近的团没什么性质。我们可以考虑建一张反图。如果这是个二分图，那么左右部恰好可以作为题中的两个 state。然而，意识到并不保证是一张连通的二分图，所以我们可以用一些连通块来拼成两个 state。那么，我们可以用个背包搞搞，再最后算算答案即可。（就不需要贪心的构造两个大小相近的团了，全部都算一遍即可）。
好题好题。
我们发现每一个点向左、向右走都是有极限的，算出得到 \((x_i, y_i)\)，其中 \(x\) 代表左边、\(y\) 代表右边。那么，把这个东西放到散点图上，发现我们本质不同的操作是一个单调不降的折线图：因为如果我们把 \(x\) 作为这个路径的「最长向左移动距离」、\(y\) 作为这个路径的「最长向右移动距离」，那么这个折线经过某个点的 \(x\) 帧或是 \(y\) 帧都将导致这个东西 GG，所以我们计算这样的折线图就可以计算对应方案了。
我们可以直接用树状数组来进行转移即可。
首先，\(n – 1\) 个二元组代表着这颗树形有向图的形状。我们先考虑外向树的情况：子树根的时间戳要早于所有的子节点，所以可以考虑直接用背包的方法进行合并。如果有反向边，那么我们可以考虑进行容斥，枚举反向关系数再乘上一个容斥系数 \(-1\) 即可。
这转化也真是妙…
首先，我们把 \((-1)^b\) 进行转换。发现转换成跟数论相关：\((-1)^b = 1 – 2(b \bmod 2)\)，则可以把这个式子弄一下：