「Codeforces Round #518」E. Random Forest Rank

Problem

Description

给定一棵 n 个点的树。
对于一个图,定义其权值为其邻接矩阵的秩。
现选择一个边集 E' \subseteq E 并将其删去,求所有 2^{n - 1} 种删边方案的权值之和。

答案对 998244353 取模。

Constraints

1 \le n \le 5 \times 10^{5}

Solution

Analysis

由基础线代知识可知一个 square matrix A 是满秩的当且仅当 \det{A}\ne 0

\det{A} = \sum_{p} \prod_{i = 1}^{n} A_{i p_{i}} \ne 0

故一个图的邻接矩阵是满秩的当且仅当 \exists p : \forall i \in \left[1, n\right] : A_{i p_{i}} \ne 0
考虑将这个排列分解成若干个互不相交的循环,则对于每个循环 \left(c_{1}, c_{2}, \dots,cq_{m}\right) ,原图中都必定存在环 \left(c_{1}, c_{2}, \dots, c_{m}\right)
注意到森林中只存在长度为 2 的环(即一条边),故一片森林的邻接矩阵是满秩的当且仅当 \exists p : \forall i \in \left[1, n\right] : \left<i, p_{i}\right> \in E 。稍加思考可以发现这个条件相当于这片森林存在完美匹配。
由基础线代知识可知一个 square matrix 的秩等于其非零主子式的最大阶数,故森林 G 的权值等于其有完美匹配的最大子图的大小,亦即其最大匹配大小的两倍。
定根,设 f_{u} 表示仅考虑以点 u 为根的子树时点 u 不在最大匹配中的概率,有转移方程:

f_{u} = \prod_{v \in \operatorname{son}{(u)}} \left(1 - \frac{f_{v}}{2}\right)

树形 DP 即可。

时间复杂度 O(n)

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
#include <cstdio>

using i64 = long long;

constexpr int maxn = 500000;
constexpr int mod = 998244353;

template <class x_tp, class y_tp>
inline void inc(x_tp &x, const y_tp &y) {
x += y; (mod <= x)$$ && (x -= mod);
}
template <typename _Tp>
inline _Tp div2(const _Tp &v) {
return ((v & 1) ? v + mod : v) >> 1;
}
template <typename _Tp>
inline int fpow(_Tp v, int n) {
_Tp pw = 1;
for (; n; n >>= 1, v = (i64)v * v % mod)
if (n & 1) pw = (i64)pw * v % mod;
return pw;
}

namespace IOManager {
constexpr int FILESZ = 131072;
char buf[FILESZ];
const char *ibuf = buf, *tbuf = buf;

struct IOManager {
inline char gc() {
return (ibuf == tbuf) && (tbuf = (ibuf = buf) + fread(buf, 1, FILESZ, stdin), ibuf == tbuf) ? EOF : *ibuf++;
}

template <typename _Tp>
inline operator _Tp() {
_Tp s = 0u; char c = gc();
for (; c < 48; c = gc());
for (; c > 47; c = gc())
s = (_Tp)(s * 10u + c - 48u);
return s;
}
};
} IOManager::IOManager io;

struct Edge {
int v; Edge *las;
inline Edge *init(const int &to, Edge *const &ls)
{return v = to, las = ls, this;}
} *las[maxn + 1];

inline void lnk(const int &u, const int &v) {
static Edge pool[maxn << 1], *alc = pool - 1;
las[u] = (++alc)->init(v, las[u]);
las[v] = (++alc)->init(u, las[v]);
}

i64 ans;

int calc(const int &u, const int &fa) {
int val = 1;
for (Edge *o = las[u]; o; o = o->las)
if (o->v != fa)
val = (i64)val * (1ll - div2(calc(o->v, u)) + mod) % mod;
ans += 1 - val;
return val;
}

int main() {
const int n = io;
for (int i = n - 1; i != 0; --i)
lnk(io, io);

calc(1, 0);
printf("%lld", ((ans % mod) + mod) * fpow(2, n) % mod);

return 0;
}