题解：P17408 【MX-X31-T4】「FAOI-R14」单人游戏

· · 题解

我们把 u 扣掉，就会出现若干连通块，记这些连通块的大小分别为 sz_1,sz_2,\dots,sz_k，那么，我们思考，如果：

怎么理解这个式子呢？ 首先，我们另 E_i 表示现在棋子在 i 这个连通块内，这次操作肯定会有一次次数，将其加上，表示这一轮。

对于 \dfrac{sz_i}{n-1}\times E_i，我们选择 y 在这个连通块的概率是 \dfrac{sz_i}{n-1}，与期望相成即为贡献。

对于 \dfrac{1-p}{n-1}\sum\limits_{j\neq i}^{}{sz_j\times E_j}，我们选择到块外面的概率为 \dfrac{sz_j}{n-1}，而这一轮不能结束的概率是 (1-p)，所以，我们从 E_j 转移。

这个式子太丑了（明明很优美），我们考虑化简。

设 S=\sum\limits_{i}{sz_i\times E_i}，则原式可化为：

E_i=1+\dfrac{sz_i}{n-1}\times E_i+\dfrac{1-p}{n-1}\times（S-sz_i\times E_i）

不妨移项，得出：

E_i-\frac{sz_i}{n-1}\times E_i+\frac{1-p}{n-1}\times sz_i\times E_i=1+\frac{1-p}{n-1}\times S

合并同类项得：

(1-\frac{sz_i}{n-1}+\frac{(1-p)\times sz_i}{n-1})\times E_i=1-\frac{1-p}{n-1}\times S

将括号内的化简，可得：

(1-\dfrac{p\times sz_i}{n-1})\times E_i=1+\frac{1-p}{n-1}\times S

将括号两边同时乘上 n-1，得：

(n-1-p\times sz_i)\times E_i=n-1+(1-p)\times S

不妨设 x=n-1+(1-p)\times S，则有：

(n-1-p\times sz_i)\times E_i=x

继续化简，得：

E_i=\dfrac{x}{n-1-p\times sz_i}

此时，我们发现：

S=\sum\limits_{i}{sz_i\times E_i}\\ =\sum\limits_{i}{sz_i\times \dfrac{x}{n-1-p\times sz_i}}\\ =x\times\sum\limits_{i}^{}{\dfrac{sz_i}{n-1-p\times sz_i}}

不妨令 y=\sum\limits_{i}^{}{\dfrac{sz_i}{n-1-p\times sz_i}}，则：

S=x\times y\\ x=n-1+(1-p)\times S=n-1+(1-p)\times x\times y

可以解得：

x-(1-p)\times x\times y=n-1\\ x=\dfrac{n-1}{1-(1-p)y}

则反代原式：

E_i=\dfrac{\dfrac{n-1}{1-(1-p)y}}{n-1-p\times sz_i}

我们终于得出了式子！！！

E_i=\dfrac{n-1}{[1-(1-p)\times y]\times(n-1-p\times sz_i)}

发现里面全都是常数项，就可以直接做了！

至于实现，倍增处理，快速确定每个点所处的连通块的大小，然后，判断具体位置，套公式即可。

正解

#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
const int N = 100005;
int n, pp, q;
vector<int> e[N];
int sz[N];
int dfn[N], rk[N], tot;
int fa[N];
int de[N];
int f[N][22];
int deg[N];
int inv_son[N], inv_fa[N];
int S[N];
int INV[N];
int qpow(int a, int b){
    int res = 1;
    a = (a % mod + mod) % mod;
    while (b){
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void dfs(int u, int pa){
    sz[u] = 1;
    f[u][0] = pa;
    fa[u] = pa;
    de[u] = de[pa] + 1;
    dfn[u] = ++tot;
    rk[tot] = u;
    for (auto v : e[u]){
        if (v == pa)
            continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> pp >> q;
    int p = pp % mod * qpow(100, mod - 2) % mod;
    for (int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    dfs(1, 0);
    for (int i = 1; i <= 20; i++)
        for (int u = 1; u <= n; u++)
            f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = 2; i <= n; i++){
        int den = ((n - 1) - p * sz[i] % mod + mod) % mod;
        inv_son[i] = qpow(den, mod - 2);
        S[f[i][0]] = (S[f[i][0]] + sz[i] % mod * inv_son[i]) % mod;
    }
    for (int i = 1; i <= n; i++){
        int tmp1 = S[i];
        if (f[i][0]){
            int tmp2 = n - sz[i];
            int den = ((n - 1) - p * tmp2 % mod + mod) % mod;
            inv_fa[i] = qpow(den, mod - 2);
            tmp1 = (tmp1 + tmp2 % mod * inv_fa[i]) % mod;
        }
        int D = (1 - (1 - p + mod) % mod * tmp1 % mod + mod) % mod;
        INV[i] = qpow(D, mod - 2);
    }
    for (int cs = 1, x, u; cs <= q; cs++){
        cin >> x >> u;
        if (deg[u] == 1){
            cout << -1 << "\n";
            continue;
        }
        int inv;
        if (dfn[u] <= dfn[x] && dfn[x] <= dfn[u] + sz[u] - 1){
            int delta = de[x] - de[u] - 1;
            int anc = x;
            for (int j = 20; j >= 0; j--)
                if ((delta >> j) & 1)
                    anc = f[anc][j];
            inv = inv_son[anc];
        }
        else{
            inv = inv_fa[u];
        }
        cout << (n - 1) % mod * inv % mod * INV[u] % mod << "\n";
    }
    return 0;
}