从 \(2024.11.05\) 之前的比赛排着刷。
CF2028 E
给定一棵树，根为 \(1\)。爱丽丝的起点位于某个顶点 \(v\) 。她想走出洞口，但不幸的是，红心皇后已经下令处死她。
每分钟都会掷一枚公平的硬币。如果硬币是正面，爱丽丝就可以移动到她当前位置的相邻顶点，反之，红心皇后就可以把爱丽丝拉到皇后选择的相邻顶点。如果爱丽丝最终出现在树的非根叶子上，那么爱丽丝就输了。
假设两人都以最佳方式移动，计算爱丽丝成功逃离每个起始顶点 \(1\le v\le n\) 的概率。对 \(998\,244\,353\) 取模的值。\(n \le 10 ^ 5\)。
首先需要一个 key observation，就是 Alice 的最优策略一定是向父亲走，红心皇后的最优策略一定是向深度最小的叶子走。设每个点深度最小的儿子是 \(s_u\)，Alice 从这个点出发逃离概率是 \(f_u\)。那么有转移：
\[f(u) = \dfrac{1}{2}(f(s_u) +f(fa_u)) \]其中 \(f(1) = 1, f(u \mid u \in \text{leaf}) = 0\)。
这个转移方式有点技巧。假设有链 \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \cdots\)。那么 \(f(2) = \dfrac{1}{2} f(1) + \dfrac{1}{2} f(3)\)。
接下来有 \(f(3) = \dfrac{1}{2} f(2) + \dfrac{1}{2} f(4) = \dfrac{1}{4} f(1) + \dfrac{1}{4} f(3) + \dfrac{1}{2} f(4)\)。移项整理得到 \(f(3) = \dfrac{1}{3} f(1) +\dfrac{2}{3} f(4)\)。
同样操作可以发现规律 \(f(i) = \dfrac{i}{1} f(1) + \dfrac{i - 1}{i} f(i + 1)\)。
首先将树按照浅儿子剖成若干链，对链单独转移，然后再对链顶单独转移即可。预处理逆元可以做到线性。
int f[N], n, m, fa[N], dep[N], s[N];
vector<int> E[N];
void dfs(int u, int F) {
fa[u] = F; for (auto v : E[u]) if (v ^ F) {
dfs(v, u); if (!dep[u]) dep[u] = dep[v] + 1, s[u] = v;
else if (dep[v] + 1 < dep[u]) s[u] = v, dep[u] = dep[v] + 1;
}
}
void dp(int u, int t, int d) {
if (!s[u]) return; dp(s[u], t, d + 1);
f[u] = (d * qpow(d + 1) % mod * f[s[u]] % mod + qpow(d + 1) * t % mod) % mod;
for (auto v : E[u]) if ((v ^ fa[u]) and (v ^ s[u])) dp(v, f[u] % mod, 1);
}
void sub() {
read(n);
rep(i, 1, n) E[i].clear(), dep[i] = 0, s[i] = 0, f[i] = 0;
rop(i, 1, n) {
int a, b; read(a, b);
E[a].push_back(b);
E[b].push_back(a);
} dfs(1, 0); f[1] = 1; dp(1, 1, 0);
rep(i, 1, n) printf("%lld ", f[i]);
return;
}