首先考虑一个朴素的 \(dp\) ，我们设\(dp_{i,j}\)表示以\(i\)为根的子树全部变成\(b_j\)最少要进行多少操作，容易得到转移
最终复杂度\(O(n^2)\)，是不足以通过的
我们发现\(dp\)的第二维状态很浪费，因为我们发现我们并不在乎染成每个颜色时的状态，而只在乎值最小的\(dp_v\)能染成颜色的集合
那我们不妨直接找出这些集合，即设\(dp_u\)表示以\(u\)为根的子树内所有叶子染成相同颜色需要的最少操作次数，\(M_u\)表示以\(u\)点为根的子树内使叶子颜色相同的最少操作次数的能染成颜色的集合(简单的说就是把以\(u\)节点为根的子树叶子变成相同颜色且操作次数为\(dp_u\)的可以染成的颜色的集合)，注意\(M_u\)为可重集
于是我们考虑怎么递推，\(M_u=\cup_{(u,v)\in E}{M_v}\)，我们找到出现次数最多的颜色，这里不妨设它的出现次数为\(k\)，则\(f_u=\sum_{(u,v)\in E}{f_v+1}-k\)
然后用\(set\)或\(map\)维护集合，最终只需要使用\(dsu\ on\ tree\)即可做到\(O(n\log^2 n)\)
标签：颜色,CF1824C,染成,次数,为根,集合,dp From： https://www.cnblogs.com/fox-konata/p/17656873.html