首页 > BLO
开通博客写题解
头像 louhc
发表于 2019-08-24 07:31:52
思路 I.设在搜索树T中以x为根的树包含的点集为SubTree(x)。 II.这里去除割点可以理解为删除与该点相连的所有边。 III.这里提到的连通块是指当某一割点去除时：1.其中任何两个点都能相互到达 2.没有更大的连通块包含该块 当然，根据II，我们把单独的X也看做一个连通块 IV.为了方便， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 henry_y
发表于 2019-09-02 21:44:33
很巧妙的一道题。对于一个点，如果它不是割点，那么去掉之后，它的答案一定是2*(n-1)(图的连通性没有改变)。如果这个点是割点，那么割掉之后会形成（设它有t个儿子）至多t+2个联通块（t个儿子，它本身，剩下的部分）。那么对于答案的贡献就是。另外注意中间值爆 #include <bits/std 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”