[LOJ2537][PKUWC2018]Minimax

qwq

难受啊取模挂了

我真愚蠢

题意

以1为根的n个节点的有根树,每个节点最多有两个子节点。

节点x的权值为:

  • 给定权值,若x无子节点。给定权值各不相同。
  • $ p_x $ 的概率为 $ max\{son[x]\} $ , $ 1 - p_x $ 的概率为 $ min\{son[x]\} $ 。

若 1号节点有 $ m $ 种可能,权值第 $ i $ 小的为 $ V_i $ ,概率为 $ D_i $ ,求

$ \sum_{i = 1}^{m}{i \times V_i \times D_i^2} $ 。

答案对998244353取模。

思路

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#define S 32768
char buf[S];int len = 0,pos = 0;
char buf2[S],*pp = buf2;
inline char __getchar()
{
if(pos == len)pos = 0,len = fread(buf,1,S,stdin);if(pos == len)return '\0';
return buf[pos++];
}
inline void __putchar(char c) {if(pp == buf2 + S)fwrite(buf2,1,S,stdout),pp = buf2;*pp++ = c;}
inline void flush(){fwrite(buf2,1,pp - buf2,stdout);}
inline void putint(int x)
{
if(!x) {__putchar('0');return;}
if(x > 9) putint(x / 10);
__putchar((x % 10) ^ '0');
}
inline int getint()
{
int r = 0,s = 1;char c = __getchar();for(;!isdigit(c);c = __getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = __getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 300030,MOD = 998244353,alpha = 17;
inline int qpow(int a,int b)
{
int r = 1;for(;b;b >>= 1)
{
if(b & 1) r = 1LL * r * a % MOD;
a = 1LL * a * a % MOD;
}
return r;
}
inline void up(int &x,int y){if((x += y) >= MOD) x -= MOD;}
namespace SegmentTree
{
int ch[N][2],fa[N],ssiz[N],root[N],sz = 0;
int va[N * alpha],mulv[N * alpha];
int lc[N * alpha],rc[N * alpha];
inline void insert(int &k,int l,int r,int p)
{
if(!k) k = ++sz,va[k] = mulv[k] = 1;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) insert(lc[k],l,mid,p);
else insert(rc[k],mid + 1,r,p);
}
inline void pd(int k)
{
if(mulv[k] > 1)
{
va[k] = 1LL * va[k] * mulv[k] % MOD;
if(lc[k]) mulv[lc[k]] = 1LL * mulv[lc[k]] * mulv[k] % MOD;
if(rc[k]) mulv[rc[k]] = 1LL * mulv[rc[k]] * mulv[k] % MOD;
mulv[k] = 1;
}
}
}
int pm[N],w[N],n;
struct node{int v,id;inline bool friend operator < (const node &a,const node &b){return a.v < b.v;}}no[N];int ncnt = 0;
namespace Extended_SegmentTree_Operation
{
using namespace SegmentTree;
int mxa = 0,mxb = 0;
inline int merge(int a,int b,int p)
{
if(!a && !b) return 0;
pd(a);pd(b);
if(!a)
{
up(mxb,va[b]);
int tmp = (mxa + p - 2LL * mxa * p) % MOD;
mulv[b] = 1LL * mulv[b] * tmp % MOD;
if(mulv[b] >= MOD) mulv[b] -= MOD;
else if(mulv[b] < 0) mulv[b] += MOD;
pd(b);
return b;
}
if(!b)
{
up(mxa,va[a]);
int tmp = (mxb + p - 2LL * mxb * p) % MOD;
mulv[a] = 1LL * mulv[a] * tmp % MOD;
if(mulv[a] >= MOD) mulv[a] -= MOD;
else if(mulv[a] < 0) mulv[a] += MOD;
pd(a);
return a;
}
rc[a] = merge(rc[a],rc[b],p);
lc[a] = merge(lc[a],lc[b],p);
va[a] = va[lc[a]] + va[rc[a]];
if(va[a] >= MOD) va[a] -= MOD;
return a;
}
inline void dfs(int u)
{
if(!ssiz[u]) return;
else if(ssiz[u] == 1)
{
dfs(ch[u][0]);
root[u] = root[ch[u][0]];
}
else
{
dfs(ch[u][0]);dfs(ch[u][1]);
mxa = mxb = 0;
root[u] = merge(root[ch[u][0]],root[ch[u][1]],pm[u]);
}
}
int ret = 0,cnt = 0;
inline void _calc(int k,int l,int r)
{
if(!va[k]) return;
pd(k);
if(l == r)
{
int v = va[k];
int ans = 1LL * (++cnt) * (1LL * w[l] * (1LL * v * v % MOD) % MOD) % MOD;
if(ans >= MOD) ans -= MOD;
if(ans < 0) ans += MOD;
up(ret,ans);
return;
}
int mid = (l + r) >> 1;
_calc(lc[k],l,mid);_calc(rc[k],mid + 1,r);
}
inline int calc(){_calc(root[1],1,ncnt);return ret;}
}
using namespace SegmentTree;
int main()
{
n = getint();
int inv = qpow(10000,MOD - 2);
for(int u = 1;u <= n;u++) fa[u] = getint(),ch[fa[u]][ssiz[fa[u]]++] = u;
for(int u = 1;u <= n;u++) if(ssiz[u]) pm[u] = (1LL * getint() * inv % MOD + MOD) % MOD;else no[++ncnt] = (node){getint(),u};
std::sort(no + 1,no + ncnt + 1);
for(int i = 1;i <= n;i++)
{
w[i] = no[i].v;
SegmentTree::insert(SegmentTree::root[no[i].id],1,ncnt,i);
}
Extended_SegmentTree_Operation::dfs(1);
putint(Extended_SegmentTree_Operation::calc());flush();
return 0;
}