賽時

先上來看T1，發(fā)現沒有什么性質，所以一定是搜索

然后考慮到n很小，所以直接搜，然后剪枝，就一定能過

大概50分鐘左右過了

然后看T2，先想了鏈和菊花的情況

但是剩下的就想不到了

能想到，大概率是個dp

但是感覺也有可能是貪心，沒怎么想

然后就想T3了

T3真的感覺很可做

開始就想到了sb2 meet-in-middle做法

然后想到了sb3 很好做，在做并查集的時候撤銷A的貢獻即可

然后想sb1 ，想建一個生成樹，然后兩邊分別跑并查集，但是寫的時候發(fā)現沒法撤銷兩邊同時的貢獻

然后就想不到了

但其實，這個單調性我是沒想到的

考慮到A答案升高，B答案一定不會增大

所以雙指針

我們一邊合并集合，一邊撤銷合并集合

考慮怎么容斥掉貢獻，考慮到維護C集合，A集合和B集合在同一個集合的點會被存在C同一個集合

給每個A集合和每個B集合給定一個哈希值，然后，HA^HB相同的在同一個C集合中

考慮合并兩個集合時，啟發(fā)式合并，同時把小的那一部分集合拿出來重新貢獻

分裂時用log的空間記錄一下原先分裂之前的點

T4考場上看了幾眼覺得不可做就扔了

賽后

100+25+0+0（T3由于題目細節(jié)沒有特判，爆0了）

聽題目時不知為何，T2和T3就是聽不懂（是我很笨么？可能是的）））

最后終于問明白了，沒有補

T2核彈做法dp

設到u剩奇鏈還是偶鏈還有剩0/1/>=2個兒子

包含了所有能影響答案的情況

然后用樹上dp經典的撤銷操作，要幾個鏈撤銷幾個貢獻（w-max原先的貢獻-現在的貢獻）這種的

所有與定義狀態(tài)沖突的都撤銷

T2貪心做法：

考慮到奇數邊和偶數邊，一定是刪少的那個更優(yōu)，因為代價為1（滿足局部最優(yōu)）

然后考慮一個點兒子奇數點還是偶數點（兒子是根據兒子的刪邊情況來判斷），特殊情況，無法判斷（f1=f2）則不產生貢獻

不能讓葉子當根