Contest 982

直接模拟即可，为了方便边界判断建议用 !=。

时间复杂度 \(O\left(n\right)\)。

\(w\) 排序来处理内向者，坐人后丢进大根堆来处理外向者。

时间复杂度 \(O\left(n\log n\right)\)。

这里讲一种直接暴力树形 DP 的做法。

令 \(f_{u,0/1}\) 表示只考虑以 \(u\) 为根的子树，\(u\) 结点所在连通块大小奇偶性，最多的删边数量。若不合法值为 \(-\infty\)。

仔细一分析你会发现 \(f_{u,0}\) 和 \(f_{u,1}\) 必定只有一个不为 \(-\infty\)（子树大小确定，不包含当前结点的连通块一定为偶数大小）。

转移时，如果儿子 \(v\) 满足 \(f_{v,0}=-\infty\)，也就是说儿子 \(v\) 与 \(u\) 必定要连边，就连。否则连不连边奇偶性不改变，断边更优。

然后就做完了，当然我一开始脑瘫了没发现性质就想得很烦，大概要不停地连两条边（不改变奇偶性）直到不优为止，也是可做的。

时间复杂度 \(O\left(n\right)\)。

剩下的题鸽掉了。

巴特西