刷题日记

Update On:2024/3/26

P8867 建造军营

显然，当且仅当桥被摧毁时图才会变成两个子图，那么可以想到 Tarjan 求边双联通，重构成一棵树。

定义 \(f_{i,0/1}\) 为强制只有根节点为 \(u\) 的子树内建筑军营，若里面有军营则，一定有被守卫的边与 \(u\) 相通。

P3225 [HNOI2012] 矿场搭建

分类讨论：

1.环

如果在一个环上，每两个点都可以互相直达，那么我们可以设置任一个点作为逃生出口，即可满足其他所有点到达这个地方。但是要考虑逃生出口坍塌的情况，所以一个环上要设置两个逃生出口，可以使无论逃生出口是否坍塌，都有一个逃生出口可用。n个点中任选两个点。

2.一般情况

割点会分整个图为多个双连通分量，我们将每个双联通分量看作整个联通块，那么一个双连通分量中只需要设置一个点，就可以满足这个分量里的点能够跑到这个出口来。同上，我们还要考虑出口坍塌的情况。在这里，因为只会坍塌一个点，所以如果出口坍塌了，割点就不会坍塌，这个分量中的其他点可以通过割点跑到另外的双连通分量中，此时等价于同一个双连通分量。我们可以继续将这些点抽象为一个概念：叶子连通块。

3.叶子连通块

叶子节点是没有出度的点，入度为1，也就是只连了一条边。那么叶子连通块的概念就是：只连接了一个割点的双连通分量。 同时，对于连接两个割点的双连通分量，其中一个割点坍塌，那么另一个割点就不会坍塌，可以通过另一个割点合并到另外一个双连通分量中。而叶子连通块就不行了，如果叶子连通块的割点（叶子的父亲）被切断，那么它就是一个单独的连通块，所以这里一定要设置一个逃生出口。在这里设置一个逃生出口，有weight种选择（weight是节点数）。根据乘法原理，最小个数是叶子连通块的个数；总方案数是所有叶子连通块的weight之积。

所以我们只需要判断一个连通块dfs后是否只找到一个割点（用del数组存起来）

Update On : 2024/3/27

P4320 道路相遇

显然如果对于两个点 \(u,v\) 如果删掉他们之间的任意一个割点，则他们一定不连通，所以割点是必经的，如果删掉非割点，由割点定义可得一定有另一条路径使得两点连通。直接建圆方树求割点即可。