[CF1830D] Mex Tree-526互联

CF1830D
贪心地想,黑白交替染色,这样每条大于1的路径的值都为2。但有些情况不优,树的形态是两棵子树中间由一条边相连,这样的最优方案是这条边上两点染1,其余点染0。
并且我们发现只用把每个同色连通块的贡献算出来,因为两个异色连通块之间的贡献为2。
最初 \(Ans=2(\frac{n(n-1)}{2}+n)=n(n+1)\)。
大小为 m,颜色为 c 的连通块减少的值为
\((\frac{n(n-1)}{2}+n)(c+1)\)。
这样就直接用树上背包计算,因为一个连通块的贡献是 \(m^2\) 级别,所以最多选 \(\sqrt{n}\) 个点。
时间 \(\Omicron(n\sqrt{n})\),空间炸了,使用 vector().swap(v) 清空内存即可。