题意
做法
先考虑暴力(O(n^2))
依次解决每个点，将该点设为根，选择了一个叶子节点相当于控制了到根路径的中点的子树
然后给每个叶子节点的控制点，然后从根bfs贪心选择
考虑优化
对于一个严格子树(S)，有(sumlimits_{xin S}deg_x=2|S|-1)，等价于(1=sumlimits_{xin S}2-deg_x)
然后就把问题转化为统计所有在控制点内点的(sum 2-deg_x)
进一步的，可以考虑每个点对一些根是否有贡献，这个随便搞个点分治就好了
先考虑暴力(O(n^2))
依次解决每个点，将该点设为根，选择了一个叶子节点相当于控制了到根路径的中点的子树
然后给每个叶子节点的控制点，然后从根bfs贪心选择
考虑优化
对于一个严格子树(S)，有(sumlimits_{xin S}deg_x=2|S|-1)，等价于(1=sumlimits_{xin S}2-deg_x)
然后就把问题转化为统计所有在控制点内点的(sum 2-deg_x)
进一步的，可以考虑每个点对一些根是否有贡献，这个随便搞个点分治就好了