题解：CF2178F Conquer or of Forest

· · 题解

思路

首先我们定义一棵子树可以被砍掉当且仅当：

这棵子树的根是整棵树的根或者这棵子树只有根这一个白色节点。

这样，我们可以把整棵树分成若干个可以被砍掉的子树。
一个重要的结论：对于一棵可以被砍掉的子树，无论它怎么接到其他节点下面，它永远都是一棵可以被砍掉的子树。
证明：因为整棵树有偶数个节点，所以接上去之后新的根节点一定是白色。设这个新的根节点为 x 点，那么对于 y 点，它的子树在换根后发生变化当且仅当 y 在原子树中 x 到根的路径上。对于这些 y 点，它们的子树少了 x 所在的那一棵子节点的子树。加上了已它父节点为根向上沿伸的那一大棵子树。设 siz_i 为原子树中 i 节点的子树大小，如下图，y 新的子树大小为 siz_{rt}-siz_z。而 siz_{rt} 为偶数，siz_z 为奇数，所以 y 新的子树大小一定是奇数，故 y 是黑色节点。

那么我们把根所在的可以被砍掉的子树大小记为 a_0，设其余的可以被砍掉的子树数量为 k，那么我们定义一个序列 a，a_i 表示第 i 个可以被砍掉的子树大小为 a_i。我们发现，我们在固定一个 a 序列的排列后，把这棵树征服的方案数为 \prod_{i=1}^{k} a_i \cdot a_{i-1}=a_0 \cdot a_k \cdot \prod_{i=1}^{k-1}a_i^2。注意这里的排列是把 a_1 到 a_k 按一种顺序排列，与 a_0 无关。
证明：我们在安排完前 i(i \le k) 棵子树后，白色节点一定是在根到某个点的路径上，第 i+1 棵子树可以以任意根接在第 i 棵子树任意一点的下方，第 i+1 棵子树有 a_i 个点，每个点都可以做这棵子树的根接到第 i 棵子树上，而第 i 棵子树有 a_{i-1} 个点，每个点都可以被接上去，故而接第 i+1 棵子树时的方案数为 a_{i+1} \cdot a_i，总的方案数用乘法原理计算，即 \prod_{i=1}^{k} a_i \cdot a_{i-1}。
我们发现，不同的排列，方案数中只有 a_k 是变化的，其余部分都是固定的。那么我们可以把上面的式子转化为 \frac{a_0 \cdot \prod_{i=1}^{k}a_i^2}{a_k}。我们枚举这里的 a_k 是具体的哪一个子树，那么其余的子树可以以任意顺序排列，排列的方案数为 (k-1)!，于是我们可以预处理 w=a_0 \cdot \prod_{i=1}^{k} a_i^2,v=(k-1)!，便可以得到最终答案为：\sum_{i=1}^{k}{\frac{w \cdot v}{a_i}}。

时间复杂度

因为 k 肯定不超过 n，所以是\mathcal{O}(t \cdot n)。

代码实现

AC link


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define unll unsigned long long
#define bint __int128
#define set_q priority_queue
#define unmp unordered_map
mt19937_64 mrand((unll) std::chrono::steady_clock::now().time_since_epoch().count());

inline ll in () { ll x = 0; bool f = false; char ch = getchar(); while (ch < '0' || ch > '9') {f |= ch == '-'; ch = getchar();} while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return f ? -x : x; }

const ll p = 998244353, inf = 1ll << 60ll, infless = -(1ll << 60ll);

inline ll quickpow (const ll &a, const ll &n) { ll res = 1ll, t = a; for (ll y = n; y > 0; y >>= 1) { if (y & 1) { res = t; res %= p; } t = t; t %= p; } return res; }

const int N = 300100, M = 520;

int test, n, c[N], sz[N], len, a[N]; vector<int> edges[N]; bool b[N]; ll ans = 0ll, res, s[N], inv[N];

inline void dfs (const int &x) { b[x] = true; c[x] = 1; sz[x] = 1; for (auto y : edges[x]) { if (!b[y]) { dfs(y); c[x] ^= c[y]; if (c[y]) { sz[x] += sz[y]; } } } if (!c[x] && x != 1) { a[++len] = sz[x]; } }

inline void solve () { ans = 0ll; //solve clear ! n = in(); len = 0; for (int i = 1; i <= n; i++) { edges[i].clear(); b[i] = false; c[i] = 0; } for (int i = 1; i < n; i++) { int x = in(), y = in(); edges[x].push_back(y); edges[y].push_back(x); } dfs(1); a[0] = sz[1]; res = a[0]; for (int i = 1; i <= len; i++) { res = res a[i] % p a[i] % p; } for (int i = 1; i <= len; i++) { ans += res s[len - 1] % p inv[a[i]] % p; ans %= p; } if (!len) { ans = 1; } printf("%lld\n", ans); return; }

int main() { inv[0] = s[0] = 1ll; for (int i = 1; i <= 300000; i++) { s[i] = s[i - 1] * i % p; inv[i] = quickpow(i, p - 2); } for (test = in(); test--; solve()); return 0; }