Contest 982
A
直接模擬即可，為了方便邊界判斷建議用 !=。
時間複雜度 \(O\left(n\right)\)。
B
\(w\) 排序來處理內向者，坐人後丟進大根堆來處理外向者。
時間複雜度 \(O\left(n\log n\right)\)。
C
這裡講一種直接暴力樹形 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)\)。
剩下的題鴿掉了。
