给定一棵 \(n\) 个点的带权树，第 \(i\) 条边的权值是 \(p_i\)。每条边初始具有一个颜色，是黑色或白色。
接下来会进行 \(k\) 次操作。一次操作会随机选定一条边 \(x\)，其中第 \(i\) 条边被选中的概率是 \(\frac{p_i}{\sum_{i=1}^{n-1} p_i}\)。然后会反转 \(x\) 的颜色：若 \(x\) 原来为黑色则变为白色，反之亦然。
定义一棵树的权值是：只保留黑色边后，每个连通块的大小的乘积。
你需要输出操作结束后树的权值的期望的结果。答案对 \(998244353\) 取模。
我们考虑钦定第 \(i\) 条边被选中了 \(t_i\) 次。
那么这种情况发生的概率就是：
\[{k\choose t_1,t_2,\cdots,t_{n-1}}\prod_{i=1}^{n-1}(\dfrac{p_i}{\sum_{i=1}^{n-1}p_i})^{t_i}
\]
提取一些系数
\[\dfrac{k!}{(\sum_{i=1}^{n-1}p_i)^k}\prod_{i=1}^{n-1}\dfrac{p_i^{t_i}}{t_i!}
\]
（在下文的讨论中我们将忽略 \(\dfrac{1}{(\sum_{i=1}^{n-1}p_i)^k}\) 这个系数)
这个时候我们会发现左边就是一个 \(\text{EGF}\) 的形式
\[\exp(x)=e^x=1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots
\]
因为边最终的颜色只跟被选中次数的奇偶性有关，所以我们分别考虑选中奇数或者偶数次的 \(\text{EGF}\)。
奇数：
\[{1\over2}(\exp(x)-\exp(-x))=\dfrac{e^x-e^{-x}}{2}=x+\dfrac{x^3}{3!}+\dfrac{x^5}{5!}+\cdots
\]
偶数：
\[{1\over2}(\exp(x)+\exp(-x)))=\dfrac{e^x+e^{-x}}{2}=1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots
\]
我们最后将所有的边的 \(\text{EGF}\) 乘起来，会得到这样的形式：
\[F(x)=\sum c_ie^{ix}
\]
答案就是 \(k![x^k]F(x)\)，我们展开它……
\[\begin {align}& k![x^k]F(x) \\
=& k![x^k]\sum c_ie^{ix} \\
=& k!\sum c_i[x^k]e^{ix} \\
=& k!\sum c_i\dfrac{i^k}{k!} \\
=& \sum c_ii^k
\end {align}
\]
因此我们只需要在 dp 时维护 \(e^ix\) 的系数即可！
（代码展示环节）
#include <algorithm>
#include <iostream>
#include <vector>using std::cin, std::cout;
const int N = 3007, O = 998244353, inv2 = (O+1)/2;
typedef long long i64;#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define rek(i,a,b) for(int i(a);i<(b);++i)
#define len(a) ((int)a.size())i64 fpow(i64 x, int k) {i64 r = 1;for(; k; k >>= 1, x = x * x %O)if(k & 1) r = r * x %O;return r;
}
#define inv(x) (fpow((x),O-2))#ifdef jianyu
#define assert(x) do{if(!(x)){cout<<"assert fail: "<<#x<<"\n";exit(0);}}while(0)
#else
#define assert(x)
#endifint n, k;auto incr = [](auto& x, auto&& y) {x += y; if(x >= O) x -= O;};
auto mult = [](auto& x, auto&& y) {(x *= y) %= O;};std::vector<int> gr[N];
int Co[N], Pr[N], Xor[N], idx;
inline void link(int x, int y, int p, int c) {++idx, Co[idx] = c, Pr[idx] = p, Xor[idx] = x^y, gr[x].push_back(idx), gr[y].push_back(idx);}struct polynomial: std::vector<i64> {using std::vector<i64>::vector; // inherit construction functionint T;inline void shift(int offset) {T += offset;}
};inline polynomial operator + (const polynomial& a, const polynomial& b) {polynomial c(std::max(a.T+len(a),b.T+len(b))-std::min(a.T, b.T));c.T = std::min(a.T, b.T);rek(i, 0, len(a)) incr(c[i + a.T - c.T], a[i]);rek(i, 0, len(b)) incr(c[i + b.T - c.T], b[i]);return c;
}inline polynomial operator - (const polynomial& a, const polynomial& b) {polynomial c(std::max(a.T+len(a),b.T+len(b))-std::min(a.T, b.T));c.T = std::min(a.T, b.T);rek(i, 0, len(a)) incr(c[i + a.T - c.T], a[i]);rek(i, 0, len(b)) incr(c[i + b.T - c.T], O-b[i]);return c;
}inline polynomial operator * (const polynomial& a, const polynomial& b) {polynomial c(a.size() + b.size() - 1);c.T = a.T + b.T;rek(i, 0, len(a)) {if(a[i]) rek(j, 0, len(b))incr(c[i+j], a[i] * b[j] %O);}return c;
}inline polynomial exp(int c, int p) {polynomial a(1, c);a.T = p;return a;
}std::pair<polynomial, polynomial>
dfs(int u, int fa) {polynomial f0(1, 1), f1(1, 1);f0.T = f1.T = 0;for(int& x: gr[u]) {int c = Co[x], v = Xor[x] ^ u, p = Pr[x];if(v == fa) continue;polynomial white = exp(inv2, p) - exp(inv2, -p);polynomial black = exp(inv2, p) + exp(inv2, -p);if(c) std::swap(white, black);auto [v0, v1] = dfs(v, u);polynomial g = white * v1 + black * v0;f1 = f1 * g + black * f0 * v1;f0 = f0 * g;}return {f0, f1};
}i64 psum;int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> k;for(int t = n, x, y, p, c; --t; ) {cin >> x >> y >> p >> c;link(x, y, p, c), incr(psum, p);}auto [f, g] = dfs(1, 0);i64 ans = 0;rek(i, 0, len(g)) {incr(ans, g[i] * fpow(i+g.T, k) %O);}cout << ans * fpow(inv(psum), k) %O << "\n";
}
25.08.09
upd 25.12.11
一样套路的题：CF2174F
给定点的颜色，对每一类颜色的点的总度数有奇偶性限制。求随机树满足条件的概率。
用 EGF 刻画每一个颜色的答案。最后乘起来算总贡献即可。
想必看过上文的都能场切这个题了吧！