[Codeforces613D]Kingdom and its Cities(虚树,树型动态规划)

发布于 2018-05-27  194 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[Codeforces613D]Kingdom and its Cities(虚树,树型动态规划)

Description

Meanwhile, the kingdom of K is getting ready for the marriage of the King's daughter. However, in order not to lose face in front of the relatives, the King should first finish reforms in his kingdom. As the King can not wait for his daughter's marriage, reforms must be finished as soon as possible.
The kingdom currently consists of n cities. Cities are connected by n - 1 bidirectional road, such that one can get from any city to any other city. As the King had to save a lot, there is only one path between any two cities.
What is the point of the reform? The key ministries of the state should be relocated to distinct cities (we call such cities important). However, due to the fact that there is a high risk of an attack by barbarians it must be done carefully. The King has made several plans, each of which is described by a set of important cities, and now wonders what is the best plan.
Barbarians can capture some of the cities that are not important (the important ones will have enough protection for sure), after that the captured city becomes impassable. In particular, an interesting feature of the plan is the minimum number of cities that the barbarians need to capture in order to make all the important cities isolated, that is, from all important cities it would be impossible to reach any other important city.
Help the King to calculate this characteristic for each of his plan.

Tag

虚树,树型动态规划

题目大意

给出一棵树,每次选出若干个点作为关键点,问至少需要割掉多少个非关键点才能使得所有的关键点不连通。

解决思路

首先肯定是把每一次询问单独提出来建立虚树,在虚树上动态规划。
无解的情况就是两个关键点直接相连,这个可以输入后就直接判掉。
需要割点的情况有两种,一是当前点不是关键点,但其儿子中有超过$1$个是关键点,那么这个点一定要割掉;二是当前点是关键点,那么它的每一个儿子中有关键点的都要割掉。动态规划的时候对这两种情况分别讨论。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[Codeforces613D]Kingdom and its Cities(虚树,树型动态规划)


HNCJ OIer