CF1823F Random Walk 题解

namespace lowspeed_song {

int deg[N], inv[N];
vector<int> adj[N];

inline void init() {
    inv[0] = inv[1] = 1;
    for (int i = 2; i < N; ++i) inv[i] = mod - inv[mod % i] * (mod / i) % mod;
}

int f[N], K[N], B[N], n, s, t;
inline void dfs(int u, int fa) {
    if (u == s) B[u] = 1;
    for (int &v : adj[u]) if (v != fa) {
        dfs(v, u);
        K[u] = (K[u] + K[v] * inv[deg[v]] % mod) % mod;
        B[u] = (B[u] + B[v] * inv[deg[v]] % mod) % mod;
    } K[u] = (1 - K[u] + mod) % mod, K[u] = inversion(K[u]);
    B[u] = B[u] * K[u] % mod, K[u] = K[u] * inv[deg[fa]] % mod;
}

inline void dfs2(int u, int fa) {
    f[u] = (f[fa] * K[u] % mod + B[u]) % mod;
    for (int &v : adj[u]) if (v != fa) dfs2(v, u);
}

inline void sol() {
    cin >> n >> s >> t;
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        adj[a].emplace_back(b), adj[b].emplace_back(a);
        ++deg[a], ++deg[b];
    } dfs(t, 0), dfs2(t, 0), f[t] = 1;
    for (int i = 1; i <= n; ++i) cout << f[i] << ' ';
    cout << '\n';
}

} // namespace lowspeed_song