首先我们有一些发现，一个点在操作过一次后再操作第二次时周围一圈点都已经归零，意味着操作第二次时该点的权值会直接去反，那么这个点的正负性是可以任意变化的，这也就意味着一个点的周围假如没有其他点的存在，这个点的正负性是自由的。那么我们的最优化目标是尽量让点对最终的答案贡献的正负性与答案的正负性尽量的相同，而且最优化是否取到极值与判定一些点的正负贡献是否合法的难度实际上是等价的，这启发我们先考虑枚举 \(2^n\) 的正负状态，判定这个正负状态是否合法。
注意到一次消除实际上是将一个 \(+\) 与一圈 \(-\) 或一个 \(-\) 与一圈 \(+\)，但在消除完后会产生很多的 \(0\)，而这些 \(0\) 在删去后所对应的子树是几乎独立的，因为一个点的周围一圈都已归零，正负状态可以任意变化，可以将其相加。但一个问题是这样会导致分裂的子树无法确定其究竟选哪个点作为根节点，这样导致了状态数实际上很多。
对此我们尝试想象已经归零的节点为一个广义的通配符 \(?\)，那么每一次消除时允许 \(?\) 自由变为 \(0\) 与 \(1\) 中的任意一个，每次将一个一个点与周围的一圈点均变 \(?\)，如果全部能变成 \(?\) 则合法，至此我们得到了一个 \(O(2^n)\) 的解法。
但一个问题是这样的增广实际上是不好设计状态的，一个启发时考虑增广的过程的形态：一开始将一些点给染黑，然后每一个黑点进行 \(\texttt{bfs}\) 扩展，扩展出一颗树，每棵树上的兄弟节点正负性相同，根节点与其儿子正负性不同，实际上可以视为若干棵树的并。
一个错误的想法是用这些树将整棵树的边集给覆盖满，但这样意味着只存在一棵树，另一个错误的想法是将一些边将断开将剩下的树的答案合并，但这样所有的边断开就是一种合法方案，将它们两个在 \(\texttt{dp}\) 的过程中合并很有可能也存在一些问题。
一个发现是导致该问题的出现的实质是根节点集合的自由选择，那么我们可以考虑的是对根节点再加一点限制，通过一些找规律我们可以发现如下的限制：
令根节点集合为 \(S\) ，则 \(S\) 合法的充要条件为对于任意边 \((u,v)\)，\(u,v\) 不同时属于 \(S\)。
我们考虑证明该结论，如果两个根节点相邻，那么意味着它们之间会互相的影响，导致谁都不能先操作，反之如果一个根与另一颗树的非根节点相邻，那么只要满足根在非根节点之前操作即不会出现这样的情况。注意到原图是一颗树，而这样的偏序关系是单向的，所以不会形成环，以拓扑排序的方式增广则可以得到一组合法解。
有了上述结论，我们可以考虑在 \(\texttt{dp}\) 时记录如下的状态\(:\)
\(1.\)一个点与其父亲节点之间的边不在选中的多棵树的边集中，且该节点不以根的形式出现。
\(2.\)一个点与其父亲节点之间的边不在选中的多棵树的边集中，且该节点以根的形式出现。
\(3.\)一个点与其父亲节点之间的边在多棵树的边集中形成了一条父亲向该节点的单向边。
\(4.\)一个点与其父亲节点之间的边在多棵树的边集中形成了一条该节点向父亲的单向边。
对每种状态分别 \(\texttt{dp}\) 即可做到 \(O(n)\)。
标签：一个点,texttt,独立,合法,问题,CTS2022,正负,多棵,节点 From： https://www.cnblogs.com/zhouhuanyi/p/17002860.html