原题,详见P10723。
几乎相同,我们只需要以一个需要选择的点为根,遍历子树看看有没有出现需要选择的点,然后直接去删除即可,可以看我的博客。
但是我们也可以换一种做法,用类似拓扑排序的算法。
先找到所有只连一条边且没有被选择的点,然后放进队列,接着依次取出队头遍历与它相连的点,同时记录一下是否访问,如果不是需要选择的点而且没有访问而且只连一条边,则可以删除。最后用总结点数减去可以删除的节点数即可。
赛时记录。
标签:遍历,删除,题解,Tree,Steiner,Minimum From: https://www.cnblogs.com/Lydic/p/18379058