首先对于一个点双内的点,一定可以将其边定向成一个强联通分量。所以可以将这个图缩点,问题变到了树上。
将这 \(k\) 个点在树上标记出来,我们需要选取一颗原图的子树满足叶子结点必须是这 \(k\) 个点中的点。(差不多就是建个虚树然后把父子边在原图上对应的边拉出来)
定义每个点的权值是自身与其连接的非选取树节点的点权之和,这个时候一个连通块的大小被定义为点权值和减去边权之和,问题变为包含某个点的连通块的权值最大是多少。
可以发现父亲方向和儿子方向无关,于是考虑换根 DP。这个非常简单不再阐述了。
复杂度 \(O(n+m)\)。
好麻烦啊,要建3次图