超棒的贪心构造题。可以观察到每次操作的两个叶子，充要条件是路径上匹配边和非匹配边交替出现，操作完后全部取反。首先考虑答案上界，从是否能取到上界入手，是本题的突破口。考虑操作两个叶子\(x,y\)，收益为\(dep[x]+dep[y]-2dep[\text{LCA}(x,y)]\)。若固定根\(r\)，当\(\text

MyBlogs[ARC183D]KeepPerfectlyMatched这场不打感觉亏麻了，怎么大家都不会D。首先匹配路径长度之和最大，很典的想到取重心，猜测答案上界\(\sum_idep_i\)可以取到。取完重心之后，希望不断把两个不同的子树里的点进行匹配，直到删空。因为原树本身存在完美匹配，所以找一对不同子