LOJ3399「2020-2021 集训队作业」Communication Network

看到这题第一想法就是口罩,感觉做过口罩这题的过程就很自然了。我们考虑设 $f(k)$ 表示恰好 $k$ 条边与原树相同的树的个数,$g(k)$ 表示钦定 $k$ 条边,于是:

然后现在求的就是 $\sum jg(j)$ 这个东西。类似口罩的做法,我们知道钦定 $k$ 条边的时候树的方案数量是 $n^{n-k-2} \prod d_i$ ,后面这团考虑组合意义,相当于是对每个钦定边的连通块选择一个点,前面这团就是 $n$ 的钦定块的数量次幂。再考虑 $jg(j)$ 的这个 $j$ ,仍然考虑组合意义,即从所有钦定边中选择一个边即可。

于是考虑设计 $dp[u][0/1][0/1]$ 表示 $u$ 子树之内,$u$ 所在的连通块是否被钦定过了点,以及 $u$ 整个子树是否有一个保留边被钦定即可。复杂度 $O(n)$ 即可解决问题。

这题不读优过不了。

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
109
110
111
112
113
114
115
116
117
118
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 2000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;

namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() \
(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
? EOF \
: *p1++)
inline int rd() {
int x = 0, f = 1;
char c = gc();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = gc();
}
while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
inline void push(const char &c) {
if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
*pp++ = c;
}
inline void write(int x) {
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
push( 10 );
}
}

int n , m;
int A[MAXN];
vi G[MAXN];

int Pow( int x , int a ) {
int ret = 1;
while( a ) {
if( a & 1 ) ret = ret * 1ll * x % P;
x = x * 1ll * x % P , a >>= 1;
}
return ret;
}

int dp[MAXN][2][2];
void dfs( int u , int f ) {
dp[u][0][0] = dp[u][1][0] = 1;
int t[2][2];
for( int v : G[u] ) if( v != f ) {
dfs( v , u );
memcpy( t , dp[u] , sizeof dp[u] );
mem( dp[u] );
// Not cut
dp[u][0][0] = ( dp[u][0][0] + t[0][0] * 1ll * dp[v][0][0] ) % P,
dp[u][1][0] = ( dp[u][1][0] + t[1][0] * 1ll * dp[v][0][0] ) % P,
dp[u][1][0] = ( dp[u][1][0] + t[0][0] * 1ll * dp[v][1][0] ) % P;
rep( w , 0 , 1 )
dp[u][0][1] = ( dp[u][0][1] + t[0][w] * 1ll * dp[v][0][w ^ 1] ) % P,
dp[u][1][1] = ( dp[u][1][1] + t[1][w] * 1ll * dp[v][0][w ^ 1] ) % P,
dp[u][1][1] = ( dp[u][1][1] + t[0][w] * 1ll * dp[v][1][w ^ 1] ) % P;
dp[u][0][1] = ( dp[u][0][1] + t[0][0] * 1ll * dp[v][0][0] ) % P,
dp[u][1][1] = ( dp[u][1][1] + t[1][0] * 1ll * dp[v][0][0] ) % P,
dp[u][1][1] = ( dp[u][1][1] + t[0][0] * 1ll * dp[v][1][0] ) % P;

// Cut

dp[u][0][0] = ( dp[u][0][0] + t[0][0] * 1ll * dp[v][1][0] % P * n ) % P,
dp[u][1][0] = ( dp[u][1][0] + t[1][0] * 1ll * dp[v][1][0] % P * n ) % P;
rep( w , 0 , 1 )
dp[u][0][1] = ( dp[u][0][1] + t[0][w] * 1ll * dp[v][1][w ^ 1] % P * n ) % P,
dp[u][1][1] = ( dp[u][1][1] + t[1][w] * 1ll * dp[v][1][w ^ 1] % P * n ) % P;
}
}

void solve() {
n = IO::rd();
rep( i , 2 , n ) {
int u , v;
u = IO::rd() , v = IO::rd();
G[u].pb( v ) , G[v].pb( u );
}
dfs( 1 , 1 );
int as = dp[1][1][1] * 1ll * Pow( n , P - 2 ) % P * 2 % P;
cout << as << endl;
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2021/03/21/loj33992020-2021-ji-xun-dui-zuo-ye-communication-network/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog