DDOSvoid's Blog

2022牛客多校3 D Directed

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/33188/D

简要题意：给定一棵 $n$ 个点以 $1$ 为根的树，现在随机使 $k$ 条边变成单向边，方向为从儿子指向父亲，问从 $s$ 出发随机游走到 $1$ 的期望步数

$n\le 10^6$

Solution

如果我们不考虑随机将 $k$ 条边定向，那么这就是一个经典问题，我们从 $v$ 走到父亲 $u$ 的期望步数为 $2sz_v-1$，我们定义从 $s$ 走到 $1$ 的这条路径为 $L$，同时规定 $L$ 不包含 $1$，那么答案就是 $\sum_{u\in L}(2sz_u-1)$

我们考虑将边定向，如果 $(v,u)$ 这条边在路径 $L$ 上，我们将 $(v,u)$ 这条边定向，那么相当于将 $u$ 的子树大小减掉 $sz_v$，不妨令 $u$ 的父亲为 $a$，那么如果 $(u,a)$ 这条边没有被定向，那么 $a$ 的子树大小也要减掉 $sz_v$，所以 $(v,u)$ 这条边的贡献大概是一个组合数前缀和的形式；如果 $(v,u)$ 不在路径上，我们只需要把它贡献到它在路径上的第一个祖先的位置即可，贡献的系数同样也是一个组合数前缀和的形式

时间复杂度 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#define maxn 1000010
#define ll long long
using namespace std;

const int p = 998244353;
ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

ll fac[maxn], inv[maxn];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
}

ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; } 

int n, k, s;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dep[maxn], f[maxn], sz[maxn];
void dfs(int u, int fa) {
    sz[u] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dep[v] = dep[u] + 1; f[v] = u; dfs(v, u); sz[u] += sz[v];
    }
}
    
bool vis[maxn]; ll P[maxn], ans, sum;
void Dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == f[u]) continue;
        if (vis[v]) {
            if (u != 1) sum = (sum + 2 * sz[v] * P[dep[v] - dep[1] - 1]) % p;
            Dfs(v, v); 
        } else {
            if (u != 1) sum = (sum + 2 * sz[v] * (P[dep[v] - dep[1] - 1] - P[dep[v] - dep[fa] - 1])) % p;
            Dfs(v, fa); 
        }
    }
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k >> s; init_C(n); ans = sum = 0; 
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    } dep[1] = 1; dfs(1, 1);
    int x = s; while (x != 1) vis[x] = 1, ans = (ans + 2 * sz[x] - 1) % p, x = f[x];
    if (!k) return cout << ans << "\n", 0;
    for (int i = 1; i < n; ++i) P[i] = (P[i - 1] + C(n - 1 - i, k - 1)) % p;
    Dfs(1, 1); ans = (ans - sum * pow_mod(C(n - 1, k), p - 2)) % p; cout << (ans + p) % p << "\n";
    return 0;
}