省选-圆方树

给一个无向图。求一个独立集，使得只保留和独立集相连的边，图仍然连通。

这道题我们按照 dfs 的顺序选，能选就选。

证明就用归纳法，对于每一个 $i$ 都能保证做完这个操作后连通。

首先，为了让问题更简单，需要钦定变量顺序，我们设 $a\le b\le c$，然后需要满足 $a$ 和 $b$ 即可，因为我们如果选了 $c$，可以通过拆分 $c$ 来得到 $a$ 或者 $b$，所以只弄 $a$ 和 $b$ 是最优的。

然后我们发现这个图有点复杂了，于是我们先考虑树的情况，我们发现我们需要让树存在一条边，切掉之后左边大小 $\ge a$，右边 $\ge b$，即存在 $[a,n-a]$ 的子树。

然后由于 $a\le b\le \frac{n}{2}$，所以我们想到了重心。我们先找到重心，然后，如果有解一定存在一个子树大小大于等于 $a$，然后剩下的拆成 $b$ 就行了。

然后树的情况就做完了，我们想想图怎么做。

我们先建出 dfs 树，然后找出重心（类比刚才的特殊情况）。如果存在一个子树大小 $\ge a$ 就直接可行，否则我们需要考虑返祖边。

考虑返祖边就是看这个子树中的节点连接到的重心的祖先。具体写法就是直接向上，然后限制不能走重心。

以重心为根，每个子树（块）大小 $< a$。利用返祖边（连接重心祖先和重心儿子），可将多个子树连通。依次累加子树大小直至总和 $\ge a$，将这些子树与重心一同作为 $A$，则 $|A| < 2a$（因每个子树 $< a$，累加刚达 $a$ 时总和 $< a+a = 2a$）。

证明：由 $n = a+b+c \ge 2a+b$ 得 $n - |A| > b$。剩余部分点数 $> b$，且原图连通，故剩余点中必有一连通块大小 $\ge b$，取为 $B$。

所以那个 $a\le b\le c$ 的限制也限制了 $a$ 和 $b$ 的量级，从而更好地找到子集。

首先，我们发现毛毛虫不能有环，所以先缩环。然后就变成了一个树上问题。

这时候，我们会猜结论：选直径！

怎么证明？我们模拟一下过程，就会发现叶子节点是不会合并的，直接合并父节点就行了。所以我们需要保留最多的父节点，于是就选直径了。

首先这道题肯定和割点有关。

对于每一个点双，我们发现，如果这个点双连接了两个及以上割点，都可以跑到别的点双里面。

然后否则就在这个点双中建立一个逃生点。方案数 $sz-1$。

然后如果没有割点，就是独立的，需要两个救生点，所以就是 $sz\times (sz-1)$。

if(low[v]>=dfn[x]){
				g[x]=1;
				child++;
				dcc++;
				while(s.top()!=v){
					d[dcc].push_back(s.top());
					s.pop();
				}
//				d[dcc].push_back(x);
				d[dcc].push_back(s.top());
				s.pop();
				d[dcc].push_back(x);
			}

注意：两个点也要算作点双。

首先，对于每一个 $s$ 和 $f$，我们的答案就是两点的所有路径中的点的并集大小减二。

然后我们想到这个问题在树上更方便求解，于是我们需要圆方树。

此时我们可以把方点设为这个点双的大小。但是这时候我们发现，方点之间会有共同的节点，也就是割点，所以我们需要将路径中的圆点的权值设成 $-1$，然后路径中的权值和就是路径的节点个数了。

令 $w_i$ 为点权，对于节点 $i$，两个点都在子树中的情况：

$2\times \sum size_j\times (size_i-size_j)$

然后我们发现这会有很多的重复的，就利用刚刚的点权进行容斥：$2\times \sum size_j\times (size_i-size_j)\times w_i$

这样就能避免割点被重复统计。

还有就是这三个点互不相同，由于方点，会重复计算，所以直接在圆点就抵消掉。

建出圆方树可以直接做，用 $sum$ 表示非割边的前缀和。

将原图转化为圆方树（原图中的点为圆点，每个点双连通分量建一个方点）。

在圆方树上，圆点权值为 $1$，方点权值为 $0$，并将点权转化为到父节点的边权（便于路径求和）。

对于每个询问的点集 $S$，将其按 DFS 序排序，计算相邻点（包括首尾）在树上的路径权值和，总和除以 $2$ 得到包含所有 $S$ 的最小连通子图的边权和。

这里不建出虚树了，就用虚树的思想。

加上该子图根节点（即排序后第一个与最后一个点的 LCA）的权值，得到子图中所有点的权值和，即圆点总数。

减去 $|S|$ 即得到不在 $S$ 中且删除后能使 $S$ 不连通的圆点数量。

一个写法：记录路径权值不算 $LCA$ 的，只有进入和出去会计算 $LCA$。然后对于节点 $1$ 就单独算了。

这道题首先我们发现如果有环就可以选择任意一个方向。

所以我们想到，先建出圆方树。

• 对于在同一个方点的情况：
  • 如果全是一个字母，答案就是 $0$。
  • 答案是 $C(_2^{siz})$，但是又有一种情况就是如果这个点从两边走，两边的路径上的点一边全是 $d$ 一边全是 $D$ 需要减去 $1$。
• 其他情况类似：
  • 对于普通的情况，如果一条路径同时存在白点双或黑点双，这一定可以。特殊的那种左边只有 $d$，右边只有 $D$ 的一定可以有一种让两点混的方式。

至于写法，就需要好好想想了，不然代码会很长。这里的一边全是 $d$ 一边全是 $D$ 这种情况直接判断哪个有 $d$ 和 $D$ 的入度的个数 $=2$ 即可。