Liveddd's Blog

愛にできることはまだあるかい

P8867 [NOIP2022] 建造军营

发表于 更新于 分类于
本文字数： 3.1k 阅读时长 ≈ 7 分钟

算是敲个警钟。

题外话：笔者在 NOIP2022 的考场上，因为水平并不高，给了自己一种会做 T2 的错觉，于是直接放弃可做性更强的 T3 选择暴冲 T2 。最终没有能够取得理想成绩。在此警示后人。

提供一种不太一样的 DP（？）。

很容易考虑到双连通分量缩点，再树形DP（不在树上的边我们称之为非树边）。对于 $\mathcal O(n^2)$ 有比较显然的树形背包。

考虑如何做到线性。设计状态 $f_x$ 表示在以 $x$ 为根的子树中，至少选了一个点，且与 $x$ 连通的方案数。设 $sum_x$ 表示以 $x$ 为根的子树中边的总数。考虑每个子节点 $y$ 对 $f_x$ 的贡献：选取的话贡献为 $f_y$，不选取那么子树 $y$ 中的边和 $y\to x$ 这条边可以随便选（但是点不能选），所以贡献为 $2^{sum_y+1}$。再减去一个点不选的方案数 $2^{sum_x}$ 即可。

因为子树外的边（并且除去到父亲节点的边）可以随便选取，所以对答案的贡献就是 $f_x\times2^{m-sum_x-[fa!=0]}$。

Code
 
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
using namespace std;
const int N=5e5+10,M=1e6+10,mod=1e9+7;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
int tot=1,head[N],ver[M<<1],ne[M<<1];
int num,dfn[N],low[N],bri[M<<1];
int cnt,c[N];
int a[N],b[N],sum[N];
ll f[N],ans,p[N+M];
vector<int>e[N];
inline void add(int u,int v)
{ 
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
void Tarjan(int x,int pre)
{
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            Tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y])
                bri[i]=bri[i^1]=1;
        }
        else if(i!=(pre^1))
            low[x]=min(low[x],dfn[y]);
    }
}
void prework(int x)
{
    c[x]=cnt;
    a[cnt]++;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        if(!c[y]&&!bri[i])
            prework(y);
    }
}
void dfs(int x,int fa)
{
    f[x]=p[a[x]+b[x]]%mod;//f[x]初值
    sum[x]=b[x];
    for(auto y:e[x])
    {
        if(y==fa)continue;
        dfs(y,x);
        sum[x]+=sum[y]+1;
        f[x]=f[x]*((f[y]+p[sum[y]+1])%mod)%mod;
        //y对f[x]的贡献
    }
    f[x]=(f[x]+mod-p[sum[x]])%mod;//减去一个点都不选的方案数
    ans=(ans+f[x]*p[m-sum[x]-(fa!=0)]%mod)%mod;//统计总的方案数
}
int main()
{
    read(n,m);
    for(int i=1;i<=m;i++)
    {    
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    Tarjan(1,0);
    for(int i=1;i<=n;i++)
        if(!c[i])
            cnt++,prework(i);
    for(int x=1;x<=n;x++)
    {
        for(int i=head[x];i;i=ne[i])
        {
            int y=ver[i];
            if(c[x]==c[y])b[c[x]]++;
            else e[c[x]].push_back(c[y]);
        }
    }
    for(int i=1;i<=cnt;i++)
        b[i]/=2;
    p[0]=1;
    for(int i=1;i<=n+m;i++)
        p[i]=(p[i-1]<<1)%mod;
    dfs(1,0);
    printf("%lld\n",ans%mod);
    return 0;
}