题面

给定连通图，需要选定至少一个关键点，然后保护至少一条边，被保护的边不会被破坏，需要保证无论破坏哪条边都不会影响关键点之间的连通性。求方案数。

Solution

这题我感觉还是有点难度的，主要是细节很多，如果不是我写的太麻烦了的话，感觉评个紫应该比较合理（不过似乎洛谷上西西弗的题难度评级都偏低一些

$\xi$ $\epsilon$ $2^{\xi}$ $2^\xi \times (2^\epsilon - 1)$ 。

$12 - 14$ 的部分分，如果想通了树形 DP，再缩个点之后就直接可以切了。

$dp(p, 0/1)$ $p$ $p$ $p$ 连通，这个继续讨论下去就会发现如果不这样设定就无法转移了。

$p$ $son$ ，首先显然有：

d p (p, 0) ⟵ d p (p, 0) \times d p (s o n, 0) \times 2

$dp(p, 1)$ 的转移：

$dp(son, 0)$ $p$ 点必须设为关键点。

d p (p, 1) ⟵ d p (p, 1) \times d p (s o n, 0) \times 2

$dp(son, 1)$ $p$ 为关键点的，则桥必须被保护。

d p (p, 1) ⟵ d p (p, 1) \times d p (s o n, 1)

$p$ $dp(p, 0)$ $p$ 连通。

d p (p, 1) ⟵ d p (p, 1) + d p (p, 0) \times d p (s o n, 1)

$dp(p, 0/1)$ $dp(p, 0/1)$ $dp(p, 1)$ $dp(p, 0)$ 。

于是我们就发现，这东西假了。。

$p$ $p$ $p$ $p$ $p$ 的边无论是否保护都是合法的，但是我们却忽略了，所以此时要考虑维护一下这个东西。

$dp(p, 0/1/2)$ $p$ 所在子树，子树内没有关键点，或有关键点且要求子树外没有关键点，或有关键点且不要求子树外没有关键点。当然这个东西写起来要多考虑一些东西，所以我们也可以换个思路，直接尝试去补上漏下的。

$s_p$ $1$ $dp(p, 1)$ $dp(p, 1) \times 2^{s_1 - s_p}$ ，也就是子树内设置关键点，子树外不设置关键点，则子树外的所有边都是任意的。然后你会发现这个东西又假了。。

$p \longleftrightarrow fa$ $dp(fa, 1)$ $p \longleftrightarrow fa$ $dp(p, 1) \times 2^{s_1 - s_p - 1}$ 。

$dp(1, 1)$ 。

至此，这道细节巨多的题就做完了。

Code


xxxxxxxxxx
138
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (ll)(1e9 + 7)
23

24
template < typename T = int >
25
inline T read(void);
26

27
struct Edge{
28
    Edge* nxt;
29
    Edge* rev;
30
    int to;
31
    bool vis;
32
    OPNEW;
33
}ed[4100000];
34
ROPNEW(ed);
35
Edge* head[1100000];
36
Edge* ehead[1100000];
37

38
int N, M;
39
int dfn[1100000], low[1100000], eBCC(0), belong[1100000];
40
int cnte[1100000], cntv[1100000];
41
int sume[1100000];
42
bool inS[1100000];
43
ll dp[1100000][2];
44
ll pow2[2100000];
45
ll ans(0);
46

47
void Tarjan(int p = 1){
48
    static stack < int > cur;
49
    static int cdfn(0);
50
    cur.push(p); inS[p] = true;
51
    low[p] = dfn[p] = ++cdfn;
52
    for(auto i = head[p]; i; i = i->nxt){
53
        if(i->vis)continue;
54
        i->vis = i->rev->vis = true;
55
        if(!dfn[SON]){
56
            Tarjan(SON);
57
            low[p] = min(low[p], low[SON]);
58
            if(low[SON] > dfn[p]){
59
                ++eBCC;
60
                while(true){
61
                    int tp = cur.top(); cur.pop();
62
                    belong[tp] = eBCC;
63
                    inS[tp] = false;
64
                    ++cntv[eBCC];
65
                    if(tp == SON)break;
66
                }
67
            }
68
        }else if(inS[SON])
69
            low[p] = min(low[p], dfn[SON]);
70
    }
71
    if(p == 1 && !cur.empty()){
72
        ++eBCC;
73
        while(true){
74
            int tp = cur.top(); cur.pop();
75
            belong[tp] = eBCC;
76
            inS[tp] = false;
77
            ++cntv[eBCC];
78
            if(tp == p)break;
79
        }
80
    }
81
}
82
void dfs_edge(int p = 1, int fa = 0){
83
    sume[p] = cnte[p];
84
    for(auto i = ehead[p]; i; i = i->nxt){
85
        if(SON == fa)continue;
86
        dfs_edge(SON, p);
87
        sume[p] += sume[SON] + 1;
88
    }
89
}
90
void MakeDP(int p = 1, int fa = 0){
91
    dp[p][0] = pow2[cnte[p]];
92
    dp[p][1] = (pow2[cntv[p]] - 1) * pow2[cnte[p]] % MOD;
93
    for(auto i = ehead[p]; i; i = i->nxt){
94
        if(SON == fa)continue;
95
        MakeDP(SON, p);
96
        dp[p][1] = (dp[p][1] * dp[SON][0] * 2 % MOD + dp[p][1] * dp[SON][1] % MOD + dp[p][0] * dp[SON][1] % MOD) % MOD;
97
        dp[p][0] = dp[p][0] * dp[SON][0] * 2 % MOD;
98
    }(ans += (p == 1 ? dp[p][1] : dp[p][1] * pow2[sume[1] - sume[p] - 1] % MOD)) %= MOD;
99
}
100

101
int main(){
102
    N = read(), M = read();
103
    pow2[0] = 1;
104
    for(int i = 1; i <= 2010000; ++i)pow2[i] = pow2[i - 1] * 2 % MOD;
105
    for(int i = 1; i <= M; ++i){
106
        int s = read(), t = read();
107
        head[s] = new Edge{head[s], npt, t};
108
        head[t] = new Edge{head[t], npt, s};
109
        head[s]->rev = head[t], head[t]->rev = head[s];
110
    }Tarjan();
111
    for(int p = 1; p <= N; ++p)
112
        for(auto i = head[p]; i; i = i->nxt)
113
            if(belong[p] != belong[SON])
114
                ehead[belong[p]] = new Edge{ehead[belong[p]], npt, belong[SON]};
115
            else ++cnte[belong[p]];
116
    for(int i = 1; i <= eBCC; ++i)cnte[i] >>= 1;
117
    dfs_edge();
118
    MakeDP();
119
    printf("%lld\n", ans);
120
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
121
    return 0;
122
}
123

124
template < typename T >
125
inline T read(void){
126
    T ret(0);
127
    int flag(1);
128
    char c = getchar();
129
    while(c != '-' && !isdigit(c))c = getchar();
130
    if(c == '-')flag = -1, c = getchar();
131
    while(isdigit(c)){
132
        ret *= 10;
133
        ret += int(c - '0');
134
        c = getchar();
135
    }
136
    ret *= flag;
137
    return ret;
138
}

UPD

update-2022_11_29 初稿

P8867 [NOIP2022] 建造军营 Solution

更好的阅读体验戳此进入

题面

Solution

Code

UPD