CF1146F - Leaf Partition

Solution

感覺做這種細節很多的分類討論樹形dp還是有點亂。

大概有一個$naive$的想法是，我們令$f_{x,0/1}$表示以$x$為根的子樹，$x$結點有沒有顏色的方案數。

然后如果存在兩個有顏色的兒子，則$x$的顏色可以直接確定。

但是直接這樣不好轉移（因為當前無色的點可能在更淺的地方和其他點連通導致有了顏色），我們修改狀態為$f_{x,0/1/2}$，$0$表示$x$無色，$1$表示我們欽定了$x$為一種它兒子的顏色，$2$表示$x$有一種確定的顏色。

那么
$$\begin{gathered} f_{x,0}=\prod _v{f}_{v,0}+f_{v,2} \\ {f}_{x,1}=(\prod _v{f}_{v,0}+f_{v,2})(\sum _v\frac{f_{v,2}}{f_{v,0}+f_{v,2}})+(\prod _v{f}_{v,0}+f_{v,2})(\sum _v\frac{f_{v,1}}{f_{v,0}+f_{v,2}}) \\ {f}_{x,2}=(\prod _v{f}_{v,0}+f_{v,1}+f_{v,2}+f_{v,2})?(\prod _v{f}_{v,0}+f_{v,2})?(\prod _v{f}_{v,0}+f_{v,2})(\sum _v\frac{f_{v,1}+f_{v,2}}{f_{v,0}+f_{v,2}}) \end{gathered}$$

時間復雜度$O(nlgn)$（快速冪）。

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 << 62) - 1; const int MAXN = 200005; const int mods = 998244353; const int MX = 100000; const int inv2 = (mods + 1) >> 1; 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;st[++ n] = '\0';}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 --]);}inline void putstr(string st) {for (int i = 0; i < (int)st.size() ; ++ i) putc(st[i]);}struct Flusher_{~Flusher_(){flush();}} io_Flusher_; } using FastIO :: read; using FastIO :: putc; using FastIO :: putstr; using FastIO :: reads; using FastIO :: print;int f[MAXN][3]; vector<int> e[MAXN]; int upd(int x, int y) { return x + y >= mods ? x + y - mods : x + y; } int quick_pow(int x, int y) {int ret = 1;for (; y ; y >>= 1) {if (y & 1) ret = 1ll * ret * x % mods;x = 1ll * x * x % mods;}return ret; } void tree_dp(int x) {for (auto v : e[x]) tree_dp(v);if (!e[x].size()) { f[x][0] = f[x][1] = 0, f[x][2] = 1; return; }f[x][0] = 1;int mul = 1, Mul = 1, sum = 0;for (auto v : e[x]) {f[x][0] = 1ll * f[x][0] * upd(f[v][0], f[v][2]) % mods;f[x][1] = upd(f[x][1], 1ll * upd(f[v][1], f[v][2]) * quick_pow(upd(f[v][0], f[v][2]), mods - 2) % mods);int t = upd(f[v][0], f[v][2]), invt = quick_pow(t, mods - 2);mul = 1ll * mul * t % mods;Mul = 1ll * Mul * upd(upd(f[v][0], f[v][1]), upd(f[v][2], f[v][2])) % mods;sum = upd(sum, 1ll * invt * upd(f[v][1], f[v][2]) % mods);}f[x][1] = 1ll * f[x][1] * f[x][0] % mods;f[x][2] = upd(Mul, mods - upd(mul, 1ll * mul * sum % mods)); // cout << x << ":" << e[x].size() << " " << mul << " " << Mul << " " << sum << " " << f[x][0] << " " << f[x][1] << " " << f[x][2] << endl; } signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin); #endif int n;read(n);for (int i = 2, x; i <= n ; ++ i) read(x), e[x].PB(i);tree_dp(1);print(upd(f[1][0], f[1][2]));return 0; }

總結

以上是生活随笔為你收集整理的CF1146F - Leaf Partition(树形dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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