CF1824C
原题
翻译
首先考虑一个朴素的 \(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\)
但是还没有结束，我们可以发现\(M_u\)的定义和我们把\(M_v\)并上来得到的\(M_u\)定义不同，因为合并后的\(M_u\)考虑了所有可能成为答案的方案，但我们只想要所有是答案的方案，所以我们要遍历一遍集合\(M_u\)，如果里面的元素出现个数\(=k\)，则我们把它的值赋值成1，否则变成0
然后用\(set\)或\(map\)维护集合，最终只需要使用\(dsu\ on\ tree\)即可做到\(O(n\log^2 n)\)
如果实现的好的话可以把叶子的权值离散化一下，可以消掉\(map\)的一个\(\log\)，最终可做到\(O(n\log n)\)
此题的关键在于发现第二维状态没什么用
zmy直接一眼秒了，\(\color{#ff0033}{\huge{wssb}}\)