2016-2017 ACM-ICPC, NEERC, Northern Subregional Contest G Gangsters in Central City (LCA)

题意:

有一棵树,水源在根节点1,房子在叶子节点。有若干操作,操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水,可以通过切断边实现(如果某个叶子节点到根节点的路径上有一条边被切掉,那么就不能供水了。)对于每次操作后,问不给所有歹徒供水最少要切多少条边,并且问在切满足前面最小的情况下,最少使得多少个良民受影响。初始没有歹徒。

思路:

 

我们先考虑第一个问题。容易知道,假设与根相连的有k条边,那么最多只需要切k次,就切断了所有房子的水源。

也就是说,从最少切的次数角度的考虑,切与水源相连的边一定是最优的。

我们可以考虑把树根1去掉,这样得到k棵子树

然后可以预处理出,对于每个叶子节点,其非根的最远祖先是谁,也就是k棵子树的根节点都是谁。

那么对于每次出现歹徒,假设其非根的最远祖先是x,只需要切1-x这条边即可。

 

现在考虑第二个问题,在保证问题一最小的情况下,一个比较直观的想法是,我们尽量往低了切,也就是尽量往原理根的边上切,这样才能使收到影响的良民比较少。

容易想到,一个子树上该切的点是,所有被歹徒占领的坏点的LCA。这样可以使得受到影响的良民最少。

因为我们要得到受到影响的良民的数量,所以用siz[i]维护以i为根的子树的叶子数量,以及歹徒的数量。

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

这道题的关键结论是,:树上多个点的LCA,就是DFS序最小的和DFS序最大的这两个点的LCA”

因此这题就是写个LCA就可以了,切掉的坏点的dfs序可以用个set维护下。

 

 

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz