首页 > 其他分享 >CF1389G口胡

CF1389G口胡

时间:2022-08-18 08:23:47浏览次数:64  
标签:原图 连通 选取 权值 CF1389G 树上

首先对于一个点双内的点,一定可以将其边定向成一个强联通分量。所以可以将这个图缩点,问题变到了树上。

将这 \(k\) 个点在树上标记出来,我们需要选取一颗原图的子树满足叶子结点必须是这 \(k\) 个点中的点。(差不多就是建个虚树然后把父子边在原图上对应的边拉出来)

定义每个点的权值是自身与其连接的非选取树节点的点权之和,这个时候一个连通块的大小被定义为点权值和减去边权之和,问题变为包含某个点的连通块的权值最大是多少。

可以发现父亲方向和儿子方向无关,于是考虑换根 DP。这个非常简单不再阐述了。

复杂度 \(O(n+m)\)。

好麻烦啊,要建3次图

标签:原图,连通,选取,权值,CF1389G,树上
From: https://www.cnblogs.com/lmpp/p/16597473.html

相关文章