其实已经不算新了~只不过之前*了几年，最近上小码王的NOIP冲刺班~
听说ACGO是一个学术网站，我看到最近有好多人被禁言了啊，那肯定是因为不够学术吧~
那我必须写一个学术帖了，说不定啥时候也会被封了还不知道呢？
讲什么呢？那就讲今天NOIP模拟赛的题吧~赛时不会这个知识点没拿到分TvT
那就开始吧！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
点双连通分量
声明：洛谷在这题中说，
> 一种定义是“图中任意两不同点之间都有至少两条点不重复的路径”，而另外一种是“不存在割点的图”，这两种定义存在细微差别，具体体现在两个点之间有一条连边构成的图。
但是一般情况下我们讨论的都是长度>2或者有关割点的问题，所以这里也就采用第二种定义了~
首先回顾求割点的方法：递归，若 uuu 点dfs树儿子存在 lowv≥dfnulow_v\ge dfn_ulowv ≥dfnu ，则该点为割点。
还要注意特判一下dfs到的第一个点的情况，因为它没有父亲节点，好可怜qwq（不是），所有点对于它来说 lowlowlow 一定是大的，但这并不能说明它是割点。只有当要dfs至少两次时它才是这几个dfs的块的割点。
那么点双连通分量应该怎么求呢？
我们可以用有向图强连通分量类似的方法，用栈维护强连通分量。
具体地，我们开一个栈，在递归到一个点 uuu 时，我们将它入栈。然后我们访问它的所有树儿子，如果发现这个点与树儿子 vvv 还是满足老套路 lowv≥dfnulow_v\ge dfn_ulowv ≥dfnu ，那么说明这个点是割点，与下面的节点形成一个点双联通分量。
但是这时，虽然树根可能不是割点，但它一定与下面的点构成一个点双连通分量，所以和上面的一样，不需要特判。（感觉更好写了？qwq）
这里直接偷洛谷第一篇题解的图嘿嘿，你们可以根据这张图自己理解一下OvO
我本来想写代码的，但是太懒了qwq，代码放 OIwiki 的吧：
圆方树
求出所有点双联通分量后建每个分量对应的虚点（记为“方点”），虚点与所属点双的每个点（记为“圆点”）连边，会形成一棵树。然后这棵树就相当于点双连通分量缩点之后的树，但是很好地保留了原树的形态。
懒得找例题了，直接放模拟赛题的特殊性质 B吧：
给定一张 nnn 个点 mmm 条边的无向图，其中 kkk 个点被封锁，分别为 a1,a2,...aka_1,a_2,...a_ka1 ,a2 ,...ak 。被封锁的点可以到达，但是不可以走出。定义 f(i)f(i)f(i) 代表额外封锁节点 i(i∉a)i(i\not\in a)i(i∈a) 后，从 111 开始可以到达的被封锁点的数量。对于 i=1,2,3,...,ni=1,2,3,...,ni=1,2,3,...,n，分别求出 f(i)f(i)f(i) 的值。如果不存在，输出 −1-1−1。
听起来是不是很难？我当时也是这么想的，但是经过我苦苦思考两个小时，还是想出来了大概解法，我真厉害！
考虑先在图中删除所有 aia_iai ，并对删除后的图跑个点双连通分量。根据定义，显然如果封锁的点在点双连通分量的内部，则不会影响，都能到达（除了一开始就被其他 aia_iai 堵住的）；否则被封锁的点一定是割点。
现在的问题转化成了，删除这个点后，有多少个 aia_iai 会被影响不能到达。
赛时的想法是，直接对点双缩点建树，大力分讨，但我毕竟是新手啊，不会写太长的代码ToT，而且当时也不会求点双连通分量，最后只能拿0分了，好悲惨。
我们考虑对这个图建一棵圆方树，则 aia_iai 被影响当且仅当这个点在原图中所有邻居在圆方树 →1\to 1→1 的路径的公共点中，由于这是一棵树，所以显然是以 111 为根，所有邻居的LCA →1\to 1→1 的路径。
然后做个树上差分即可。
所以，有了圆方树，再难的问题，也能变简单！
说完了，下课！！！哈哈哈哈哈哈哈哈哈！
