「PKUWC2018」Minimax - 线段树合并

给你一棵 $n$ 个结点的二叉树，定义结点 $x$ 的权值为：

1. 若 $x$ 没有子结点，那么它的权值会在输入里给出，保证这类点中每个结点的权值互不相同。

2. 若 $x$ 有子结点，那么它的权值有 $p_x$ 的概率是它的子结点的权值的最大值，有 $1-p_x$的概率是它的子结点的权值的最小值。

假设 $1$ 号结点的权值有 $m$ 种可能性，权值第 $i$ 小的可能性的权值是 $V_i$，它的概率为 $D_i$，求：

$(\sum_{i=1}^{m}i\cdot V_i\cdot D_i^2)~ \mathrm{mod}~998244353$

$n\le 3*10^5, w_i\le10^9$

Links

LOJ2537

Solution

首先考虑$n^2$dp，设$dp[x][i]$表示$x$号点取到排名为$i$权值的概率

通过枚举两个儿子的权值直接转移是$O(n^3)$的，用前缀和优化就变成$O(n^2)$的了

转移式为

$\begin{aligned} dp[x][i] = &\sum_{son=0}^{1}dp[ch[x][son]][i] \times Pre[son\oplus 1][i-1]\times p[x]\\ +&dp[ch[x][son]][i]\times Suf[son\oplus1][i + 1]\times(1-p[x]) \end{aligned}$

然后考虑优化

通过观察dp方程可以发现这是一个很经典的套路

注意到转移实际上有两个限制，一是合并子树信息，二是与权值排名大小有关的一个限制

因此可以用线段树合并来优化，需要维护一个区间乘标记

代码中的$sumx,sumy$就是分别维护两棵子树的$Pre[][]\times p[x]+Suf[][]\times(1-p[x])$

一个这么傻逼的地方我理解了好久，对线段树合并的理解还是不太够啊。。。

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 3e5 + 100, Mod = 998244353;

inline int Pow (int a, int b)
{
	int ans = 1;
	while (b) { if (b & 1) ans = 1ll * ans * a % Mod; a = 1ll * a * a % Mod; b >>= 1; }
	return ans;
}

int N, inv = Pow(10000, Mod - 2);
int ch[Maxn][3], son[Maxn], fa[Maxn], P[Maxn], A[Maxn], Hash[Maxn];
int Root[Maxn * 20], sum_leaf;

namespace SEG
{
#define ls Tree[root].ch[0]
#define rs Tree[root].ch[1]
#define lson ls, l, mid
#define rson rs, mid + 1, r
	int node_cnt;
	struct tree
	{
		int ch[2], sum, tag;
	}Tree[Maxn * 20];

	inline void push_up (int root) { Tree[root].sum = (Tree[ls].sum + Tree[rs].sum) % Mod; }

	inline void push_down (int root)
	{
		if (Tree[root].tag <= 1) return ;
		Tree[ls].tag = 1ll * Tree[ls].tag * Tree[root].tag % Mod;
		Tree[ls].sum = 1ll * Tree[ls].sum * Tree[root].tag % Mod;
		Tree[rs].tag = 1ll * Tree[rs].tag * Tree[root].tag % Mod;
		Tree[rs].sum = 1ll * Tree[rs].sum * Tree[root].tag % Mod;
		Tree[root].tag = 1;
	}

	inline void update (int &root, int l, int r, int x, int val)
	{
		if (!root) root = ++node_cnt, Tree[root].tag = 1;
		if (l == r) { Tree[root].sum = val; return ; }
		int mid = l + r >> 1;
		push_down(root);
		if (x <= mid) update (lson, x, val);
		else update (rson, x, val);
		push_up(root);
	}

	inline int merge (int x, int y, int sumx, int sumy, int p)
	{
		if (!y) { Tree[x].sum = 1ll * Tree[x].sum * sumy % Mod; Tree[x].tag = 1ll * Tree[x].tag * sumy % Mod; return x; }
		if (!x) { Tree[y].sum = 1ll * Tree[y].sum * sumx % Mod; Tree[y].tag = 1ll * Tree[y].tag * sumx % Mod; return y; }
		push_down(x), push_down (y);
		int xl = Tree[Tree[x].ch[0]].sum, xr = Tree[Tree[x].ch[1]].sum, yl = Tree[Tree[y].ch[0]].sum, yr = Tree[Tree[y].ch[1]].sum;
		Tree[x].ch[0] = merge (Tree[x].ch[0], Tree[y].ch[0], (sumx + 1ll * (1 - p + Mod) % Mod * xr % Mod) % Mod, (sumy + 1ll * (1 - p + Mod) % Mod * yr % Mod) % Mod, p);
		Tree[x].ch[1] = merge (Tree[x].ch[1], Tree[y].ch[1], (sumx + 1ll * p * xl % Mod) % Mod, (sumy + 1ll * p * yl % Mod) % Mod, p);
		push_up(x);
		return x;
	}

	inline int query (int root, int l, int r)
	{
		if (l == r) return 1ll * l * Hash[l] % Mod * Tree[root].sum % Mod * Tree[root].sum % Mod;
		int mid = l + r >> 1;
		push_down(root);
		return (query (lson) + query(rson)) % Mod;
	}
}

inline void dfs (int x)
{
	if (ch[x][0]) dfs(ch[x][0]);
	if (ch[x][1]) dfs(ch[x][1]);
	if (!son[x]) SEG :: update (Root[x], 1, sum_leaf, A[x], 1);
	else if (son[x] == 1) Root[x] = Root[ch[x][0]];
	else Root[x] = SEG :: merge (Root[ch[x][0]], Root[ch[x][1]], 0, 0, P[x]);
}

inline void Solve ()
{
	dfs(1);
	printf("%d\n", SEG :: query (Root[1], 1, sum_leaf));
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i <= N; ++i) fa[i] = read<int>(), ch[fa[i]][son[fa[i]]++] = i;
	for (int i = 1; i <= N; ++i)
	{
		if (!son[i]) A[i] = Hash[++sum_leaf] = read<int>();
		else P[i] = 1ll * read<int>() * inv % Mod;	
	}

	sort(Hash + 1, Hash + sum_leaf + 1);
	for (int i = 1; i <= N; ++i) A[i] = lower_bound(Hash + 1, Hash + sum_leaf + 1, A[i]) - Hash;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}