題目鏈接
loj2537
題解
觀察題目的式子似乎沒(méi)有什么意義，我們考慮計(jì)算出每一種權(quán)值的概率
先離散化一下權(quán)值
顯然可以設(shè)一個(gè)\(dp\)，設(shè)\(f[i][j]\)表示\(i\)節(jié)點(diǎn)權(quán)值為\(j\)的概率
如果\(i\)是葉節(jié)點(diǎn)顯然
如果\(i\)只有一個(gè)兒子直接繼承即可
如果\(i\)有兩個(gè)兒子，對(duì)于兒子\(x\)，設(shè)另一個(gè)兒子為\(y\)
則有
\[f[i][j] += f[x][j](1 - p_i)\sum\limits_{k > j}f[r][k] + f[x][j]p_i\sum\limits_{k < j}f[r][k]\]
直接轉(zhuǎn)移是\(O(n^2)\)的，發(fā)現(xiàn)每個(gè)節(jié)點(diǎn)都有\(O(n)\)個(gè)位置需要轉(zhuǎn)移
考慮優(yōu)化，可以考慮線段樹(shù)合并
對(duì)于一個(gè)子樹(shù)中的權(quán)值\(x\)，我們記另一棵子樹(shù)比它大的概率為\(maxa\)，
則\(x\)的概率要乘上\(maxa(1 - p_i) + (1 - maxa)p_i = maxa + p_i - 2p_imaxa\)
所以我們?cè)诰€段樹(shù)合并過(guò)程中，優(yōu)先合并右子樹(shù)，并更新兩棵子樹(shù)的\(maxa\)與\(maxb\)，就可以在合并過(guò)程中轉(zhuǎn)移了
復(fù)雜度\(O(nlogn)\)
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 300005,maxm = 8000005,INF = 1000000000,P = 998244353;
inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag;
}
int n,Ls[maxn],Rs[maxn],b[maxn],N,v10000;
int rt[maxn],sum[maxm],ls[maxm],rs[maxm],tag[maxm],cnt;
int p[maxn],maxa,maxb;
inline int qpow(int a,int b){int re = 1;for (; b; b >>= 1,a = 1ll * a * a % P)if (b & 1) re = 1ll * re * a % P;return re;
}
inline void pd(int u){if (tag[u] > 1){sum[ls[u]] = 1ll * sum[ls[u]] * tag[u] % P;sum[rs[u]] = 1ll * sum[rs[u]] * tag[u] % P;tag[ls[u]] = 1ll * tag[ls[u]] * tag[u] % P;tag[rs[u]] = 1ll * tag[rs[u]] * tag[u] % P;tag[u] = 1;}
}
void modify(int& u,int l,int r,int pos){u = ++cnt; sum[u] = tag[u] = 1;if (l == r) return;int mid = l + r >> 1;if (mid >= pos) modify(ls[u],l,mid,pos);else modify(rs[u],mid + 1,r,pos);
}
int merge(int u,int v,int p){if (!u && !v) return 0;if (!u){maxb = (maxb + sum[v]) % P;int tmp;tmp = (((maxa + p) % P - 2ll * p * maxa % P) % P + P) % P;sum[v] = 1ll * sum[v] * tmp % P;tag[v] = 1ll * tag[v] * tmp % P;return v;}if (!v){maxa = (maxa + sum[u]) % P;int tmp;tmp = (((maxb + p) % P - 2ll * p * maxb % P) % P + P) % P;sum[u] = 1ll * sum[u] * tmp % P;tag[u] = 1ll * tag[u] * tmp % P;return u;}pd(u); pd(v);int t = ++cnt; tag[t] = 1;rs[t] = merge(rs[u],rs[v],p);ls[t] = merge(ls[u],ls[v],p);sum[t] = (sum[ls[t]] + sum[rs[t]]) % P;return t;
}
void dfs(int u){if (!Ls[u]) modify(rt[u],1,N,p[u]);else if (!Rs[u]) dfs(Ls[u]),rt[u] = rt[Ls[u]];else {dfs(Ls[u]); dfs(Rs[u]);maxa = maxb = 0;rt[u] = merge(rt[Ls[u]],rt[Rs[u]],p[u]);}
}
int ans;
void cal(int u,int l,int r){if (l == r) {ans = (ans + 1ll * l * b[l] % P * sum[u] % P * sum[u] % P) % P;return;}pd(u);int mid = l + r >> 1;cal(ls[u],l,mid);cal(rs[u],mid + 1,r);
}
int main(){n = read(); read(); int x; v10000 = qpow(10000,P - 2);for (int i = 2; i <= n; i++){x = read();if (!Ls[x]) Ls[x] = i;else Rs[x] = i;}for (int i = 1; i <= n; i++){p[i] = read();if (!Ls[i]) b[++N] = p[i];else p[i] = 1ll * p[i] * v10000 % P;}sort(b + 1,b + 1 + N);for (int i = 1; i <= n; i++)if (!Ls[i]) p[i] = lower_bound(b + 1,b + 1 + N,p[i]) - b;dfs(1);cal(rt[1],1,N);printf("%d\n",ans);return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/9215258.html
總結(jié)
以上是生活随笔為你收集整理的loj2537 「PKUWC2018」Minimax 【概率 + 线段树合并】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
