【NOIP2022】建造军营

meteor2008 / 2023-08-21 / 原文

题面

题目描述

A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。

A 国的国土由 $n$ 座城市组成，$m$ 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。

众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 $1,000,000,007\left(10^{9}+7\right)$ 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个方案中被派兵看守而在另一个方案中没有。

输入输出与样例

输入格式

第一行包含两个正整数 $n,m$，分别表示城市的个数和双向道路的数量。

接下来 $m$ 行，每行包含两个正整数 $u_{i},v_{i}$，描述一条连接 $u_{i}$ 和 $v_{i}$ 的双向道路。保证没有重边和自环。

输出格式

输出一行包含一个整数，表示建造军营和看守道路的方案数对 $1,000,000,007\left(10^{9}+ 7\right)$ 取模的结果。

样例输入

2 1
1 2

样例输出

样例解释

A 国有两座城市，一条道路连接他们。所有可能的方案如下：

在城市 $1$ 建军营, 不看守这条道路;
在城市 $1$ 建军营, 看守这条道路;
在城市 $2$ 建军营, 不看守这条道路;
在城市 $2$ 建军营, 看守这条道路;
在城市 $1,2$ 建军营, 看守这条道路。

数据规模与约定

对所有数据，保证 $1 \leq n \leq 5 \times 10^5$，$n - 1 \leq m \leq 10^6$，$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$。

各测试点的信息如下

测试点编号	$n \leq $	$m \leq $	特殊条件
$1 \sim 3$	$8$	$10$	无
$4 \sim 7$	$16$	$25$	无
$8 \sim 9$	$3000$	$5000$	无
$10 \sim 11$	$5 \times 10^5$	$10^6$	特殊性质 $\mathrm{A}$
$12 \sim 14$	$5 \times 10^5$	$10^6$	$m = n - 1$
$15 \sim 16$	$5 \times 10^5$	$10^6$	$m = n$
$17 \sim 20$	$5 \times 10^5$	$10^6$	无

特殊性质 $\mathrm{A}$：保证 $m=n-1$ 且第 $i$ 条道路连接城市 $i$ 与 $i+1$。

题解

方法概述

先双连通分量缩点，再树上DP+容斥
建议先去熟悉一下tarjan算法以及相关概念（如割点、割边、缩点）。

部分分

测试点编号	$n \leq $	$m \leq $	特殊条件	解法
$1 \sim 3$	$8$	$10$	无	solve1
$4 \sim 7$	$16$	$25$	无	solve1
$8 \sim 9$	$3000$	$5000$	无	solve3_plus
$10 \sim 11$	$5 \times 10^5$	$10^6$	特殊性质 $\mathrm{A}$	solve2
$12 \sim 14$	$5 \times 10^5$	$10^6$	$m = n - 1$	solve3
$15 \sim 16$	$5 \times 10^5$	$10^6$	$m = n$	solve3_plus
$17 \sim 20$	$5 \times 10^5$	$10^6$	无	正解

solve[1]:暴搜

枚举所有$2^n$种军营的选法。
枚举后将得到一张“子图”，在这张“子图”中对边进行分类：哪些边是必须的，哪些边可选可不选，以此进行统计。

注意，这张“子图”实际和原图拥有完全一致的点边结构。不同的是，“子图”中的一些点被标记为军营

若可选可不选的边有$x$条，则对当前选法答案的贡献是$\times 2^x$。
（必须的边没有贡献，因为只有一种选法）

判断必须的边。
首先，可以对“子图”再进行一次简化。任意端点不是标记点的边一定是可选可不选的，因为它对“战局${^1}$”没有任何影响。（1：“战局”即军营的连通性）
于是，在进行统计之后，可将战局外的边和点忽略，得到一张“真·子图”。

接下来考虑如何在“真·子图”中进行边的分类。

这时会发现一个性质。

注意，并非是此性质需要前文的推断作为基础。实际上，只有当我们产生“分类边”这一需求，才会“顺理成章”地得出这一性质）

必须的边都是“真·子图”中的割边，可选可不选的边都是“真·子图”中的非割边。
这一点根据割边的定义得出，不需要证明。

对“真·子图”进行一次tarjan，就可以完成分类以及统计。
（关于tarjan算法，此处不多赘述）

这里说这么多是因为这个性质会从头用到尾

考虑时间复杂度。
进行$2^n$次枚举。每次枚举跑一遍tarjan，是$O(n)$的复杂度。
共是$O(n2^n)$复杂度。$n\leq 16$，则$n2^n$约为$1e6$。
是挺正确的时间复杂度。

solve[2]：链上解

利用特殊性质。
数据保证图是一条链，实际上是将求边的难度降低了。
与solve[1]情况不同的是，可以简单的排除掉$2^n$中的许多不合法情况。对于一条链，保证连通性的也只会是一条子链，或者说一个子区间。此时，只需要头尾两个端点就能确定边的情况。

求[l,r]对答案的贡献。
先抛开枚举不谈，假使已经确定了一个区间[l,r]。
此时可选可不选的边是[1,l]和[r,n]的边，必选的是[l,r]的边。
统计答案时，只需要边的数量，而不需要具体的边。
贡献应当是：

\[sum = 2^{l+n-r-1} \]

事实上，还忽略了一个东西。
即使在这个区间[l,r]中，所有边都必须选中，点却不一定。所以答案还要$\times 2^{l-r-1}$。（只有l和r本身必选）
于是有：

\[sum = 2^{l+n-r-1}\times 2^{l-r-1} = 2^{n-2} \]

所以这个答案和l、r压根没关系嘛。

答案和时间复杂度。
l和r的可能配对统共有$C_{n}^{2}$种。
于是乎，答案就是：

\[ans = C_{n}^{2}\times 2^{n-2} \]

是一个类似于O(1)解决的时间复杂度。

solve[3]:树上DP

其实已经极其接近正解了，不会有人只写树上DP却不写正解吧。（？
于是决定放在正解部分说明。

solve[3]_plus：树上DP_plus

测试点8~9
进行缩点的树上背包DP。
（而不是正解里更优的DP，不打算细嗦）
$f(u,i)$表示当前节点$u$、选了$i$个军营的情况数。

测试点15~16
比起solve[3]多的一条边会形成一个环。
对这个环进行特判可以解决。（虽然有点麻烦）
正解也可以解决。（不那么麻烦）

正解做法

（只是其中一种做法，仅供参考）

想在前面

会发现“环”是一个挺关键的麻烦。
前面的性质也提到了“割边”，其实隐隐约约就能感觉到正解的方向了。
像这种计数题肯定是用DP解决无疑的，但是给出的图又不保证是树。
要DP肯定还得是树上DP，所以要尝试把图变成树。

这不就巧了吗，又是环，又是割边，又是图变成树……
于是就双连通分量缩点，利用所有条件解决所有问题，挺完美的。

P.S.其实我做题的时候是卡在这里的，如下

：话说为什么可以缩点啊，即使是双连通分量，难道对于其中的部分点时一定不会是必选吗？
：它是个环啊！是个环啊！环！
：（连滚带爬）

P.S.当我还在摸鱼写题解的时候，勤奋的同学已经怒切下一道了，恐怖如斯QAQ

缩点

其实直接缩就可以。
对于每个新点记一下包含了多少原来的点，包含了多少原来的边。
缩点时需要记哪些东西，一般都可以毛估估出来。
或者一开始就多记一点也无所谓，不影响，而且比较保险。

树上DP

缩点之后就只剩下割边了，也就是说，图变成了树。
于是就可以快乐的树上DP。（DP还是多练练，熟悉下解题思路）

状态定义：
$f(u,1)$表示点$u$的子树中至少选了一个军营，并且军营和$u$连通的情况数。
$f(u,0)$表示点$u$的子树中不选军营的情况数。

在考虑转移前先考虑答案统计。

注意，DP优先证明正确性，但是可以仅仅脑内自证，不详细写出。正因如此，这里仅仅是考虑答案统计，而不是答案统计

对于每个节点，只统计子树外无军营且不选u的树边情况下的答案。
联系到状态定义，就可以保证不重不漏。

这里额外补充一点定义：
$sumV(u)$表示缩点后节点$u$包含的点数
$sumE(u)$表示缩点后节点$u$包含的边数
$sumS(u)$表示缩点后节点$u$子树的边数
$fa(u)$表示缩点后节点$u$的父亲节点

状态转移：

\[f(u,0) = 2^{sumE(u)}\times \Pi_{fa(v)=u}{2 f(v,0)}\\ f(u,1) = \sum_{fa(v)=u}{f(u,0)\times f(v,1)+f(u,1)\times(2f(v,0)+f(v,1))} \]

代码实现中要注意$f(u,1)$转移的先后顺序。
应当先乘再加，或者提前存储$f(u,1)$的值。

初始化状态：

\[f(u,0) = 2^{sumE(u)}, f(u,1) = 2^{sumV(u)+sumE(u)}-2^{sumE(u)} \]

答案统计：
设根节点为$rt$（root的简写），缩点后树的点集为$V$

\[ans = \sum_{u\in V \and u \not= rt}{f(u,1)\times 2^{sumS(rt)-sumS(u)-1}}+f(rt,1) \]

根节点的话，一般是选$1$，不过其实选哪个都差不多。