网站怎么做备案变更,成都哪些地方好玩,seo网站推广实例,wordpress+sql+导入数据库备份CF1146F - Leaf Partition
Solution
感觉做这种细节很多的分类讨论树形dp还是有点乱。
大概有一个naivenaivenaive的想法是#xff0c;我们令fx,0/1f_{x,0/1}fx,0/1表示以xxx为根的子树#xff0c;xxx结点有没有颜色的方案数。
然后如果存在两个有颜色的儿子#xff0…CF1146F - Leaf Partition
Solution
感觉做这种细节很多的分类讨论树形dp还是有点乱。
大概有一个naivenaivenaive的想法是我们令fx,0/1f_{x,0/1}fx,0/1表示以xxx为根的子树xxx结点有没有颜色的方案数。
然后如果存在两个有颜色的儿子则xxx的颜色可以直接确定。
但是直接这样不好转移因为当前无色的点可能在更浅的地方和其他点连通导致有了颜色我们修改状态为fx,0/1/2f_{x,0/1/2}fx,0/1/2000表示xxx无色111表示我们钦定了xxx为一种它儿子的颜色222表示xxx有一种确定的颜色。
那么 fx,0∏vfv,0fv,2fx,1(∏vfv,0fv,2)(∑vfv,2fv,0fv,2)(∏vfv,0fv,2)(∑vfv,1fv,0fv,2)fx,2(∏vfv,0fv,1fv,2fv,2)−(∏vfv,0fv,2)−(∏vfv,0fv,2)(∑vfv,1fv,2fv,0fv,2)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}}}})fx,0v∏fv,0fv,2fx,1(v∏fv,0fv,2)(v∑fv,0fv,2fv,2)(v∏fv,0fv,2)(v∑fv,0fv,2fv,1)fx,2(v∏fv,0fv,1fv,2fv,2)−(v∏fv,0fv,2)−(v∏fv,0fv,2)(v∑fv,0fv,2fv,1fv,2)
时间复杂度O(nlgn)O(nlgn)O(nlgn)快速幂。
Code
#include bits/stdc.husing namespace std;templatetypename T inline bool upmin(T x, T y) { return y x ? x y, 1 : 0; }
templatetypename 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 pairint, int PR;
typedef vectorint 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;}templateclass Iinline 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;}templateclass Iinline 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];
vectorint 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;
}
