E – Independence
这道题直接去想性质不好想，因为贪心的话、找到两个大小相近的团没什么性质。我们可以考虑建一张反图。如果这是个二分图，那么左右部恰好可以作为题中的两个 state。然而，意识到并不保证是一张连通的二分图，所以我们可以用一些连通块来拼成两个 state。那么，我们可以用个背包搞搞，再最后算算答案即可。（就不需要贪心的构造两个大小相近的团了，全部都算一遍即可）。
这道题直接去想性质不好想，因为贪心的话、找到两个大小相近的团没什么性质。我们可以考虑建一张反图。如果这是个二分图，那么左右部恰好可以作为题中的两个 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)\)，则可以把这个式子弄一下：
想了半天都不知道怎么刻画状态，后面发现可以转成一个泛化问题，就比较好理解了。
考虑不严格地减去最小值、而是任意值，并达到题目要求的结果。这个问题肯定不会更优，而最优解可以直接作为本题最优解。
为啥我看到了 C# 代码（那是我逝去的青春）。
首先知道肯定是 SAM，但是你我都知道在线性构造的时候树的形态会变，所以没法维护根点权值和。所以加上一个 LCT 弄一下即可。