题意
给定一棵由 \(n\) 个节点组成的树，定义每次移动的方式为等概率的移动到相邻节点上，询问从 \(s\) 移动到 \(t\) 的过程中每个点的期望经过次数。
（\(1 \le n \le 2 \times 10^5\)）。
题解
定义 \(f_i\) 为节点 \(i\) 的期望经过次数，\(fa_u\) 为节点 \(u\) 的父亲节点，\(\operatorname{deg}_u\) 表示节点 \(u\) 的度数，\(\operatorname{son}_u\) 表示节点 \(u\) 的子节点集合。
我们记路径 \(s \rightarrow t\) 上的点为 \(k_0, k_1, k_2, \cdots k_m\)，其中 \(k_0 = s, k_m = t\)。我们可以发现对于任意 \(r_i\) 在去除路径上的边连接的子树后都会形成一棵以自己为根的有根树，记为 \(\operatorname{subtree}_{r_i}\)。通过观察可以发现，对于这类子树叶子节点 \(v\)，有
\[f_v = \dfrac{1}{\operatorname{deg}_{fa_v}} f_{fa_v} \]考虑推广这一结论，对于在子树中的节点 \(u\)，有 \(f_u = \dfrac{\operatorname{deg}_u}{\operatorname{deg}_{fa_u}} f_{fa_u}\)，下面给出数学归纳法的证明
\[\begin{aligned} f_u &= \sum\limits_{\left(u, v\right) \in E} \dfrac{1}{\operatorname{deg}_v}f_v \\ &= \sum\limits_{v \in \operatorname{son}_u} \dfrac{1}{\operatorname{deg}_v}f_v + \dfrac{1}{\operatorname{deg}_{fa_u}}f_{fa_u} \\ &= \sum\limits_{v \in \operatorname{son}_u} \dfrac{1}{\operatorname{deg}_v} \dfrac{\operatorname{deg}_v}{\operatorname{deg}_u} f_u + \dfrac{1}{\operatorname{deg}_{fa_u}} f_{fa_u} \\ &= \sum\limits_{v \in \operatorname{son}_u} \dfrac{1}{\operatorname{deg}_u} f_u + \dfrac{1}{\operatorname{deg}_{fa_u}} f_{fa_u} \\ &= \dfrac{\operatorname{deg}_u - 1}{\operatorname{deg}_u} f_u + \dfrac{1}{\operatorname{deg}_{fa_u}} f_{fa_u} \\ &= \dfrac{\operatorname{deg}_u}{\operatorname{deg}_{fa_u}} f_{fa_u} \end{aligned}\]推广该结论，设 \(v \in \operatorname{son}_u, pa = fa_u\)
\[f_v = \dfrac{\operatorname{deg}_v}{\operatorname{deg}_u} f_u = \dfrac{\operatorname{deg}_v}{\operatorname{deg}_u} \dfrac{\operatorname{deg}_u}{\operatorname{deg}_{pa}} f_{pa} = \dfrac{deg_v}{deg_{pa}} f_{pa} \]对于 \(\forall v \in \operatorname{subtree}_{u}\)，有
\[f_v = \dfrac{\operatorname{deg}_v}{\operatorname{deg}_u} f_u \]现在考虑路径 \(s \rightarrow t\) 上的点
\[\begin{aligned} f_{k_0} &= 1 + \sum\limits_{\left(k_0, v\right) \in E} \dfrac{1}{\operatorname{deg}_v}f_v \\ &= 1 + \sum\limits_{\left(k_0, v\right) \in E \land v \neq k_1}\dfrac{1}{\operatorname{deg}_v}f_v + \dfrac{1}{\operatorname{deg}_{k_1}} f_{k_1} \\ &= 1 + \sum\limits_{\left(k_0, v\right) \in E \land v \neq k_1}\dfrac{1}{\operatorname{deg}_v}\dfrac{\operatorname{deg}_v}{\operatorname{deg}_{k_0}} f_{k_0} + \dfrac{1}{\operatorname{deg}_{k_1}} f_{k_1} \\ &= 1 + \dfrac{\operatorname{deg}_{k_0} - 1}{\operatorname{deg}_{k_0}} f_{k_0} + \dfrac{1}{\operatorname{deg}_{k_1}} f_{k_1} \\ &= \operatorname{deg}_{k_0} \left(1 + \dfrac{1}{\operatorname{deg}_{k_1}} f_{k_1}\right) \end{aligned}\]\[\begin{aligned} f_{k_1} &= \sum\limits_{\left(k_1, v\right) \in E} \dfrac{1}{\operatorname{deg}_v} f_v \\ &= \sum\limits_{\left(k_1, v\right) \in E \land v \neq k_0 \land v \neq k_2} \dfrac{1}{\operatorname{deg}_v}f_v + \dfrac{1}{\operatorname{deg}_{k_0}}f_{k_0} + \dfrac{1}{\operatorname{deg}_{k_2}} f_{k_2} \\ &= \sum\limits_{\left(k_1, v\right) \in E \land v \neq k_0 \land v \neq k_2} \dfrac{1}{\operatorname{deg}_v}\dfrac{\operatorname{deg}_v}{\operatorname{deg}_{k_1}}f_{k_1} + \dfrac{1}{\operatorname{deg}_{k_0}}f_{k_0} + \dfrac{1}{\operatorname{deg}_{k_2}} f_{k_2} \\ &= \dfrac{\operatorname{deg}_{k_1} - 2}{\operatorname{deg}_{k_1}} f_{k_1} + \left(1 + \dfrac{1}{\operatorname{deg}_{k_0} f_{k_1}}\right) + \dfrac{1}{\operatorname{deg}_{k_2}} f_{k_2} \\ &= 1 + \dfrac{\operatorname{deg}_{k_1} - 1}{\operatorname{deg}_{k_1}} f_{k_1} + \dfrac{1}{\operatorname{deg}_{k_2}} f_{k_2} \\ &= \operatorname{deg}_{k_1} \left(1 + \dfrac{1}{\operatorname{deg}_{k_2}} f_{k_2}\right) \end{aligned}\]同理
\[\begin{aligned} f_{k_{m - 1}} &= \operatorname{deg}_{k_{m - 1}} \left(1 + \dfrac{1}{\operatorname{deg}_{k_m}} f_{k_m}\right) \\ &= \operatorname{deg}_{k_{m - 1}} \left(1 + 0\right) \\ &= \operatorname{deg}_{k_{m - 1}} \end{aligned}\]接下来我们将该式展开
\[f_{k_{m - 2}} = \operatorname{deg}_{k_{m - 2}} \left(1 + \dfrac{1}{\operatorname{deg}_{k_{m - 2}}} f_{k_{m - 2}}\right) = 2 \cdot \operatorname{deg}_{k_{m - 2}} \]\[f_{k_{m - 3}} = \operatorname{deg}_{k_{m - 2}} \left(1 + \dfrac{1}{\operatorname{deg}_{k_{m - 3}}} f_{k_{m - 3}}\right) = 3 \cdot \operatorname{deg}_{k_{m - 3}} \]\[f_{k_{m - i}} = i \cdot \operatorname{deg}_{k_{m - i}} \]综合以上的结论可以发现，对于路径上的各个点 \(k_{m - i}\) 有
\[\forall v \in \operatorname{subtree}_{k_{m - i}}, f_v = i \cdot \operatorname{deg}_v \]可以 \(\mathcal{O}(n)\) 解决本题。
Code
//Codeforces - 1823F
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<bool> bitset;
constexpr valueType MOD = 998244353;
bool ModOperSafeModOption = false;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
}
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
}
a = a - b;
if (a < 0)
a += mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
}
return a + b >= mod ? a + b - mod : a + b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
}
return a - b < 0 ? a - b + mod : a - b;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
}
return (long long) a * b % MOD;
}
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
}
a = (long long) a * b % mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
if (ModOperSafeModOption) {
a %= mod;
b %= mod - 1;
if (a < 0)
a += mod;
if (b < 0)
b += mod - 1;
}
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
valueType N, S, T;
ValueVector ans, distance;
ValueMatrix G;
void dfs(valueType x, valueType from) {
if (x == T) {
distance[x] = 0;
return;
}
for (auto const &iter: G[x]) {
if (iter == from)
continue;
dfs(iter, x);
if (distance[iter] != -1) {
distance[x] = distance[iter] + 1;
return;
}
}
}
void calc(valueType x, valueType from, valueType k) {
ans[x] = mul(k, G[x].size());
for (auto const &iter: G[x]) {
if (iter == from)
continue;
calc(iter, x, k);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
std::cin >> N >> S >> T;
ans.resize(N + 1, 0);
distance.resize(N + 1, -1);
G.resize(N + 1);
for (valueType i = 1; i < N; ++i) {
valueType u, v;
std::cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(S, 0);
for (valueType i = 1; i <= N; ++i) {
if (distance[i] != -1) {
ans[i] = mul(distance[i], G[i].size());
for (auto const &iter: G[i])
if (distance[iter] == -1)
calc(iter, i, distance[i]);
}
}
ans[T] = 1;
for (valueType i = 1; i <= N; ++i)
std::cout << ans[i] << ' ';
std::cout << std::endl;
return 0;
}