首页 > 其他 > 详细

#4849. 图

时间:2020-06-15 23:01:17      阅读:55      评论:0      收藏:0      [点我收藏+]

题目描述

给定一张 $n$ 个点 $m$ 条边的无向联通图和其中一棵生成树,要求删掉正好两条树边和一些非树边,使得图不连通。求最少删掉几条非树边。

保证以 $1$ 号点为生成树的根时,非树边的两端的最近公共祖先是 $1$ 号点。

数据范围

$3 \le n \le 40000; m \le 100000; m \ge n − 1$

题解

考虑删掉两条边后删掉非树边,那就考虑孤立三块中的一块。

1.删掉不在以 $1$ 为根的同一子树内的边:那就要么把 $u$ 或 $v$ 子树连出去的非树边删掉,要么删掉两个子树外到这两个子树内的边。
2.如果删掉同一子树的边:可以发现 $u,v$ 构成祖先关系更优。那就是要么是孤立 $v$ 子树,要么孤立 $u$ 子树扣掉 $v$ 子树的部分,要么就是孤立 $u$ 子树外的连通块。

用 $\text{dsu on tree}$ 维护即可。效率: $O(nlog^2n)$ 。

#4849. 图

原文:https://www.cnblogs.com/xjqxjq/p/13137948.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!