P8867 [NOIP2022] 建造军营题解

容易发现，在点双中的边在任何情况下都不是必须被看守的边，于是考虑对点双联通分量缩点，下文中 $ce_i$ 表示点双 $i$ 中边的数量，$cp_i$ 表示点双 $i$ 中点的数量。

无向图缩点之后将会成为一棵树，如果选择树上的某些点，将这些点所在的连通子图中的边是必须要选的，其他边可选可不选，考虑 DP 求解。

定义 $dp(i,0)$ 表示以 $i$ 为根的子树中，一个点都不选的方案数，$dp(i,1)$ 表示以 $i$ 为根的子树中，$i$ 节点被连接的方案数。

注意，这里的「$i$ 节点被连接」 $i$ 有可能是被选中当做军营，也有可能在 $i$ 的子树中建造军营，然后通过被看守的道路使 $i$ 与军营联通。

也就是说，只要 $i$ 子树中有被当做军营的点，并且连接到了 $i$ ，那这种情况就应该被计入在 $dp(i,1)$ 中。

考虑转移：

$dp(x,0)$ 比较容易，在他的儿子 $to$ 的子树中不能选择点，$i\to to$ 的边可选可不选，所以： $$ dp(i,0)\gets dp(i,0)\times dp(to,0)\times2 $$ $dp(x,1)$ 有两种情况：

如果他的儿子 $to$ 不是第一个「有军营的子树」，$dp(x,1)$ 从 $dp(x,1)$ 转移，他的儿子 $to$ 子树中有没有军营都可以。如果有，那么 $x\to to$ 的边必须要选，如果没有， $x\to to$ 的边选不选都行，所以：

$$ dp(x,1)\gets dp(x,1)\times (dp(to,1)+dp(to,0)\times 2) $$

如果你想让他的儿子 $to$ 成为第一个「有军营的子树」，$dp(x,1)$ 从 $dp(x,0)$ 转移，他的儿子 $to$ 子树中必须有军营，那么 $x\to to$ 的边必须要选，所以：

$$ dp(x,1)\gets dp(x,0)\times dp(to,1) $$

考虑初值：$dp(i,0)=2^{ce_i},dp(i,1)=2^{ce_i}\times (2^{cp_i}-1)$。

考虑求答案:

对于每个点 $i$，考虑统计其作为所有军营的 LCA 的情况，即 $dp(i,1)$，子树外的边可选可不选，设 $i$ 子树内的边的个数为 $sum_i$（包括边双内的边），答案为 $ans\gets ans+(dp(i,1)\times 2^{m-sum_i})$ 。

但这显然不对，原因在于，我们无法保证 $i$ 作为所有军营的 LCA。

在这个图中，$6$ 节点被选中军营，蓝色边被选中看守，$1$ 号节点不是所有军营的 LCA，但这种情况却计入在 $dp(1,1)$ 中。

而相同的情况，却会在 $dp(2,1),dp(5,1),dp(6,1)$ 中统计，显然重复了。

所以，我们要在求答案的过程中，确保每个点去往其父亲的边是不被看守的，即使他不是军营的 LCA，这样统计就可以保证不重复。

$$ \left\{\begin{array}{ll} ans \leftarrow d p_{x, 1} \cdot 2^{m-sum_x-1} & x \neq 1 \\ ans \leftarrow d p_{x, 1} & x=1 \end{array}\right. $$

好的结束。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N=500010,p=1e9+7;
int n,m;
struct node{int to,num;};
vector<node>edge[N];
int dfn[N],low[N],Time;
bool br[N<<1];
void Tarjan(int x,int fa){
    dfn[x]=low[x]=++Time;
    for(auto i:edge[x]){
        if(!dfn[i.to]){
            Tarjan(i.to,x);
            low[x]=min(low[x],low[i.to]);
            if(low[i.to]>dfn[x]) br[i.num]=1;
        }else if(i.to!=fa) low[x]=min(low[x],dfn[i.to]);
    }
}
int cnt,ce[N],cp[N],bel[N];
void find(int x,int bel){
    if(::bel[x]) return;
    ::bel[x]=bel,cp[bel]++;
    for(auto i:edge[x]) if(!br[i.num]) 
        find(i.to,bel),ce[bel]++;
}
vector<int>tree[N];
ll dp[N][2],sum[N],pw[N],ans;
void dfs(int x,int fa){
    sum[x]=ce[x];
    dp[x][0]=pw[ce[x]];
    dp[x][1]=pw[ce[x]]*(pw[cp[x]]-1)%p;
    for(int to:tree[x]){
        if(to==fa) continue;
        dfs(to,x),sum[x]+=sum[to]+1;
        (dp[x][1]*=((2*dp[to][0])%p+dp[to][1])%p)%=p;
        (dp[x][1]+=dp[x][0]*dp[to][1]%p)%=p;
        (dp[x][0]*=(2*dp[to][0])%p)%=p;
    }
    if(x!=1) (ans+=dp[x][1]*pw[m-sum[x]-1])%=p;
    else (ans+=dp[x][1])%=p;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;pw[0]=1;
    for(int i=1;i<=max(n,m);i++) pw[i]=pw[i-1]*2%p;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        edge[x].push_back({y,i});
        edge[y].push_back({x,i});
    }
    Tarjan(1,0);
    for(int i=1;i<=n;i++) if(!bel[i]) find(i,++cnt),ce[cnt]=ce[cnt]/2;
    for(int x=1;x<=n;x++) for(auto i:edge[x]) 
        if(br[i.num]) tree[bel[x]].push_back(bel[i.to]);
    dfs(1,0);cout<<ans;
    return 0;
}

P8867 [NOIP2022] 建造军营 题解

P8867 [NOIP2022] 建造军营题解