「Codeforces Round #518」E. Random Forest Rank

Posted on | Edited on | In , ,

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;
}