这只蒟蒻看完题完全不会做，但是这只蒟蒻是通过百度搜索虚树找到这题的，发现这道CF *2800的题居然是许多人介绍虚树的第一道例题！我大概可以退役力！
不过看完题解觉得真的还挺可做，只是我太弱了。
首先考虑树形dp，令$f_i$表示以$i$为根的子树中使得重要城市两两不相同的最少占领个数，所以可以得到最基础的转移：$f_u=\sum_{v\in son(u)}f_v$。
但是这肯定没有结束。另外令$g_u$表示是否存在重要城市还与$u$相连。考虑分情况讨论：
1.$u$为重要城市，那么$f_u$还要加上$\sum_{v\in son(u)}g_v$
2.$u$不是重要城市，如果该点子树中有大于一个重要城市没有断，那么$u$占领了就行了，否则$g_u=1$。
因为第二种情况只会在重要城市的lca上进行，所以在虚树上dp即可完成这题啦。
标签：Kingdom,重要,城市,son,sum,CF613D,虚树 From： https://www.cnblogs.com/nebula-xy/p/17006886.html