NOIP2022T3建造军营题解
[NOIP2022] 建造军营
题目描述
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)\) 取模的结果。
对所有数据，保证 \(1 \leq n \leq 5 \times 10^5\)，\(n - 1 \leq m \leq 10^6\)
题解
首先条件反射式想到边双缩点好吧，这是必然的，对于一个边双连通分量来说，随便在哪里建造军营，在哪里选边保护都可以，那么考虑先边双缩点，然后就变成了一棵树，可以DP。
设\(size_i,edge_i\)分别表示双连通分量\(i\)所含的点数与边数，那么考虑如何推状态转移方程
则问题转化为：给定一棵树，每个点\(i\)有\(2^{edge_i}\times (2^{size_i}-1)\)种染色方式，\(2^{edge_i}\)种不染色方式的方式，每条边都可以染色，问有多少种染色方案，使得割断任意非染色边后所有染色点仍然连通
假设预处理出\(S1_i\)表示\(2^{edge_i}\),\(S2_i\)表示\(2^{size_i}\)
考虑分析性质，我们发现，如果一个节点染色，那么这个节点的子树中但凡染了色的节点，其到此节点的边都必须染色。
考虑设\(f_{i,0/1,0/1}\)表示在以节点\(i\)为根的子树中，节点\(i\)是否被染色，以及节点\(i\)的子树是否有节点被染色
则最终的答案应为：\(f_{1,0,1}+f_{1,1,1}+f_{1,1,0}\)
考虑如何求解，以下默认\(v\)是\(u\)的子节点
\[f_{u,0,0}=2S1_u\times \prod f_{v,0,0} \]解释：乘2是因为边\((u,v)\)可染可不染
\(f_{u,0,1}\)分类讨论，当它只有一个子节点的时候，为
\[f_{u,0,1}=2S1_u\times(f_{v,1,0}+f_{v,1,1}+f_{v,0,1}) \]若它有多个子节点的时候
\[f_{u,0,1}=S1_u\times \prod(f_{v,1,0}+f_{v,1,1}+f_{v,0,1}) \]那么接着
\[f_{u,1,0}=2(S1_u\times S2_u-S1)\times \prod f_{v,0,0} \]\[f_{u,1,1}=(S1_u\times S2_u-S1)\times \prod(f_{v,1,0}+f_{v,1,1}+f_{v,0,1}) \]边界：对于叶子节点来说，\(f_{u,0,0}=S1_u,f_{u,0,1}=0,f_{u,1,1}=0,f_{u,1,0}=S1_u\times S2_u-S1_u\)
标签：染色,S1,times,道路,NOIP2022T3,军营,节点 From： https://www.cnblogs.com/oierpyt/p/16942987.html