CF1067E Random Forest Rank

Solution

考慮樹的鄰接矩陣的秩的意義，不難發現相當于每個點找一個“代表”，對于一個點$x$，它的“代表”為一個與$x$相鄰的結點，要求保證所有點的“代表”不重復，求能找到“代表”的點的最大點集。

稍加思考可以發現這個最大點集等同于最大匹配的兩倍，而森林的秩等同于所有樹的秩的和，還是最大匹配的兩倍。

于是我們要求的東西相當于每個點能夠匹配的概率的和。

令$f_x$表示$x$匹配到一個兒子結點的概率。
當$x$的所有兒子結點被匹配時，$x$無法匹配。因此$x$匹配的概率為$1?\prod \frac{1+f_v}{2}$，樹形dp即可。

時間復雜度$O(n)$。

Code

#include <bits/stdc++.h>using namespace std;template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; } template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondtypedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int, int> PR; typedef vector<int> VI; const lod eps = 1e-9; const lod pi = acos(-1); const int oo = 1 << 30; const ll loo = 1ll << 60; const int mods = 998244353; const int inv2 = (mods + 1) >> 1; const int MAXN = 600005; const int INF = 0x3f3f3f3f; //1061109567 /*--------------------------------------------------------------------*/namespace FastIO{constexpr int SIZE = (1 << 21) + 1;int num = 0, f;char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf, *oT = obuf + SIZE - 1, c;#define gc() (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)), (iS == iT ? EOF : *iS ++)) : *iS ++)inline void flush() {fwrite(obuf, 1, oS - obuf, stdout);oS = obuf;}inline void putc(char c) {*oS ++ = c;if (oS == oT) flush();}inline void getc(char &c) {for (c = gc(); !isalpha(c) && c != EOF; c = gc());}inline void reads(char *st) {char c;int n = 0;getc(st[++ n]);for (c = gc(); isalpha(c) ; c = gc()) st[++ n] = c;}template<class I>inline void read(I &x) {for (f = 1, c = gc(); c < '0' || c > '9' ; c = gc()) if (c == '-') f = -1;for (x = 0; c >= '0' && c <= '9' ; c = gc()) x = (x << 3) + (x << 1) + (c & 15);x *= f;}template<class I>inline void print(I x) {if (x < 0) putc('-'), x = -x;if (!x) putc('0');while (x) que[++ num] = x % 10 + 48, x /= 10;while (num) putc(que[num --]);}struct Flusher_{~Flusher_(){flush();}} io_Flusher_; } using FastIO :: read; using FastIO :: putc; using FastIO :: reads; using FastIO :: print;vector<int> e[MAXN]; int f[MAXN], ans = 0; int upd(int x, int y) { return x + y >= mods ? x + y - mods : x + y; } void tree_dp(int x, int father) {for (auto v : e[x]) {if (v == father) continue;tree_dp(v, x);}int p = 1;for (auto v : e[x]) {if (v == father) continue;p = 1ll * p * (1 + f[v]) % mods * inv2 % mods;}f[x] = upd(1, mods - p);ans = upd(ans, f[x]); } signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin); #endifint n, pw = 1;read(n);for (int i = 1, u, v; i < n ; ++ i) read(u), read(v), e[u].PB(v), e[v].PB(u), pw = upd(pw, pw);tree_dp(1, 0);print(2ll * ans * pw % mods), putc('\n');return 0; }

總結

以上是生活随笔為你收集整理的CF1067E Random Forest Rank(树形dp，概率与期望，线性代数)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。