目录
LOJ #2537 / 洛谷 P5298 「PKUWC2018」Minimax
一棵有根二叉树 \(\mathcal T\) .
定义结点 \(x\) 的权值为:
假设 \(1\) 号结点的权值有 \(m\) 种可能性,权值第 \(i\) 小的可能性的权值是 \(V_i\),它的概率为 \(D_i\)(\(D_i>0\)),求:
\[\sum_{i=1}^m i\cdot V_i\cdot D_i^2
\]
答案对 \(998244353\) 取模 .
令 \(dp_{u, w}\) 表示点 \(u\) 的权值为 \(w\) 的概率 .
由于 \(\mathcal T\) 是二叉树,于是权值来源只可能有两个 .
设权值来源子树根为 \(a\),另一子树根为 \(b\),则:
\[dp_{u, w} = dp_{a,w}\cdot\left(p_u\cdot\sum_{w'
\]
直接 dp 是 \(O(n^2)\) 的,可以获得 40pts .
展开写,令 \(ls\) 为 \(u\) 的左儿子,\(rs\) 为右儿子,则:
\(\displaystyle\begin{aligned}dp_{u, w} &= dp_{ls,w}\cdot\left(p_u\cdot\sum_{w'=1}^{j-1}dp_{rs, w'}+(1-p_u)\sum_{w'=j+1}^mdp_{rs,w'}\right)+dp_{rs,w}\cdot\left(p_u\cdot\sum_{w'=1}^{j-1}dp_{ls, w'}+(1-p_u)\sum_{w'=j+1}^mdp_{ls,w'}\right)\\&=p_u\left(dp_{rs,w}\sum_{w'=1}^{j-1}dp_{ls, w'}+dp_{ls,w}\sum_{w'=1}^{j-1}dp_{rs, w'}\right)+(1-p_u)\left(dp_{rs,w}\sum_{w'=j+1}^mdp_{ls, w'}+dp_{ls,w}\sum_{w'=j+1}^mdp_{rs, w'}\right)\end{aligned}\)
化成这个只是为了展示这个前后缀和的形式 .
考虑线段树合并 .
维护前缀、后缀概率和,于是合并的时候可以直接算,注意合并时一棵树有某节点但另一棵树没有时相当于一个整体乘操作,打一个乘法懒标记即可 .
离散化权值之后,时空复杂度均为 \(O(n\log n)\) .
细节见代码
Code :
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <climits>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5+50, M = 40*N;
const ll P = 998244353, invS = 796898467;
template<typename T>
inline int chkmin(T& a, const T& b){if (a > b) a = b; return a;}
template<typename T>
inline int chkmax(T& a, const T& b){if (a < b) a = b; return a;}
int n, m, deg[N], son[N][2], root[N];
ll val[N];
vector<ll> G;
inline int discrete(ll w){return lower_bound(G.begin(), G.end(), w) - G.begin();}
struct SMF
{
int ch[M][2], cc;
ll sum[M], laz[M]; // mul tag (1)
inline void pushup(int u){sum[u] = (sum[ch[u][0]] + sum[ch[u][1]]) % P;}
inline void pushmul(int u, ll v){if (!u) return ; sum[u] = sum[u] * v % P; laz[u] = laz[u] * v % P;}
inline void pushdown(int u)
{
if (laz[u] == 1) return ; // none
if (ch[u][0]) pushmul(ch[u][0], laz[u]);
if (ch[u][1]) pushmul(ch[u][1], laz[u]);
laz[u] = 1;
}
inline void insert(int& u, int l, int r, int p, ll v)
{
if (!u){u = ++cc; laz[u] = 1;}
if (l == r){sum[u] = v % P; return ;}
int mid = (l + r) >> 1;
pushdown(u);
if (p <= mid) insert(ch[u][0], l, mid, p, v);
else insert(ch[u][1], mid+1, r, p, v);
pushup(u);
}
inline int merge(int x, int y, int l, int r, ll xmul, ll ymul, ll v)
{
if (!x && !y) return 0;
if (!x){pushmul(y, ymul); return y;}
if (!y){pushmul(x, xmul); return x;}
pushdown(x); pushdown(y);
int mid = (l + r) >> 1;
ll lsx = sum[ch[x][0]] % P, lsy = sum[ch[y][0]] % P, rsx = sum[ch[x][1]] % P, rsy = sum[ch[y][1]] % P;
ch[x][0] = merge(ch[x][0], ch[y][0], l, mid, (xmul + rsy * (1-v+P) % P) % P, (ymul + rsx * (1-v+P) % P) % P, v);
ch[x][1] = merge(ch[x][1], ch[y][1], mid+1, r, (xmul + lsy * v % P) % P, (ymul + lsx * v % P) % P, v); // magic
pushup(x); return x;
}
inline ll order(int x, int l, int r) // get answer
{
if (l == r) return l * G[l] % P * sum[x] % P * sum[x] % P;
pushdown(x);
int mid = (l + r) >> 1;
return (order(ch[x][0], l, mid) + order(ch[x][1], mid+1, r)) % P;
}
}T;
inline void dfs(int u)
{
if (!deg[u]) T.insert(root[u], 1, m, val[u], 1);
else if (deg[u] == 1){dfs(son[u][0]); root[u] = root[son[u][0]];}
else if (deg[u] == 2)
{
dfs(son[u][0]); dfs(son[u][1]);
root[u] = T.merge(root[son[u][0]], root[son[u][1]], 1, m, 0, 0, val[u]);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("i.in", "r", stdin);
#endif
scanf("%d", &n); G.emplace_back(-114514);
for (int i=1, x; i<=n; i++){scanf("%d", &x); son[x][deg[x]++] = i;}
for (int i=1; i<=n; i++)
{
scanf("%lld", val+i);
if (deg[i]) val[i] = val[i] * invS % P;
else G.emplace_back(val[i]); // leaf
}
stable_sort(G.begin(), G.end());
G.erase(unique(G.begin(), G.end()), G.end());
m = G.size() + 1;
for (int i=1; i<=n; i++)
if (!deg[i]) val[i] = discrete(val[i]);
dfs(1);
printf("%lld\n", T.order(root[1], 1, m));
return 0;
}
链接形式 ref .
手机扫一扫
移动阅读更方便
你可能感兴趣的文章