题解 P5298 【[PKUWC2018]Minimax】

好妙的一个题… 我们设 $f_{i,j}$ 为 $i$ 节点出现 $j$ 的概率 设 $l = ch[i][0] , r = ch[i][1]$ 即左儿子右儿子 设 $m$ 为叶子结点的个数 显然，$i$ 出现 $j$ 的概率为 $$f_{i,j} = f_{l,j} * (p_i \sum_{k=1}^{j-1}f_{r,k} + (1-p_i)\sum_{k=j+1}^{m}f_{r,k}) + f_{r,j} * (p_i \sum_{k=1}^{j-1}f_{l,k} + (1-p_i)\sum_{k=j+1}^{m}f_{l,k})$$ 不难发现，这个柿子有关前缀和和后缀和，可以用线段树合并的操作来进行转移，从下到上转移，求出根节点的概率就好了… ```cpp #include <cstdio> #include <algorithm> int read() { int x = 0; char c = 0; while (c < 48) c = getchar(); while (c > 47) x = (x << 1) + (x << 3) + (c & 15), c = getchar(); return x; } const int mod = 998244353; int qpow(int x, int y) { int ans = 1; for (; y; y >>= 1, x = 1ll * x * x % mod) if (y & 1) ans = 1ll * ans * x % mod; return ans; } int n; const int maxn = 3e5 + 10; int ch[maxn][2], fa[maxn], cnt[maxn], val[maxn], tmp[maxn], qwq = 0, s[maxn]; int rt[maxn], ls[maxn << 5], rs[maxn << 5], sum[maxn << 5], mul[maxn << 5]; int ans = 0, tot = 0; void pushup(int rt) { sum[rt] = (sum[ls[rt]] +sum[rs[rt]]) % mod; } void pushmul(int rt, int v) { if (!rt) return; sum[rt] = 1ll * sum[rt] * v % mod; mul[rt] = 1ll * mul[rt] * v % mod; } void pushd(int rt) { if (mul[rt] == 1) return; if (ls[rt]) pushmul(ls[rt], mul[rt]); if (rs[rt]) pushmul(rs[rt], mul[rt]); mul[rt] = 1; } int newnode() { int x = ++ tot; ls[x] = rs[x] = sum[x] = 0, mul[x] = 1 ; return x ; } void upd(int& p, int l, int r, int x, int v) { if (!p) p = newnode() ; if (l == r) { sum[p] = v; return; } pushd(p); int mid = l + r >> 1; (x <= mid) ? upd(ls[p], l, mid, x, v) : upd(rs[p], mid + 1, r, x, v); pushup(p); } int merge(int x, int y, int l, int r, int xmul, int ymul, int v) { if (!x && !y) return 0; if (!x) { pushmul(y, ymul); return y; } if (!y) { pushmul(x, xmul); return x; } pushd(x), pushd(y); int mid = l + r >> 1; int lsx = sum[ls[x]], lsy = sum[ls[y]], rsx = sum[rs[x]], rsy = sum[rs[y]]; ls[x] = merge(ls[x], ls[y], l, mid, (xmul + 1ll * rsy % mod * (1 - v + mod)) % mod, (ymul + 1ll * rsx % mod * (1 - v + mod)) % mod, v); rs[x] = merge(rs[x], rs[y], mid + 1, r, (xmul + 1ll * lsy % mod * v) % mod, (ymul + 1ll * lsx % mod * v) % mod, v); pushup(x); return x; } void out(int x, int l, int r) { if (!x) return; if (l == r) { s[l] = sum[x]; return; } int mid = l + r >> 1; pushd(x); out(ls[x], l, mid); out(rs[x], mid + 1, r); } void dfs(int u) { if (!cnt[u]) upd(rt[u], 1, qwq, val[u], 1); if (cnt[u] == 1) dfs(ch[u][0]), rt[u] = rt[ch[u][0]] ; if (cnt[u] == 2) dfs(ch[u][0]), dfs(ch[u][1]), rt[u] = merge(rt[ch[u][0]], rt[ch[u][1]] ,1 , qwq , 0 , 0 , val[u]); } int main() { n = read(); for (int i = 1; i <= n; i++) fa[i] = read(); for (int i = 1; i <= n; i++) if (fa[i]) ch[fa[i]][cnt[fa[i]]++] = i; for (int i = 1; i <= n; i++) val[i] = read(); for (int i = 1; i <= n; i++) { if (cnt[i]) { val[i] = 1ll * val[i] * qpow(10000, mod - 2) % mod; } else { tmp[++qwq] = val[i]; } } std ::sort(tmp + 1, tmp + qwq + 1); for (int i = 1; i <= n; i++) if (!cnt[i]) val[i] = std ::lower_bound(tmp + 1, tmp + qwq + 1, val[i]) - tmp; dfs(1); out(rt[1], 1, qwq); for (int i = 1; i <= qwq; i++) ans = (ans + 1ll * i * tmp[i] % mod * s[i] % mod * s[i]) % mod; printf("%d\n", ans); return 0; } ```