题解
\(f_{u,k}\) 节点 \(u\) 是第 \(k\) 小的点的概率。
\(deg = 2\) 的情况：
\[f_{u,k}=(1-p_u)\left(f_{lc,k}\sum_{k'>k}f_{rc,k'}+f_{rc,k}\sum_{k'>k}f_{lc,k'}+f_{lc,k}f_{rc,k}\right) +p_u\left(f_{lc,k}\sum_{k'<k}f_{rc,k'}+f_{rc,k}\sum_{k'<k}f_{lc,k'}+f_{lc,k}f_{rc,k}\right) \]因为题目保证点权互不相同，所以
\[f_{u,k}=(1-p_u)\left(f_{lc,k}\sum_{k'>k}f_{rc,k'}+f_{rc,k}\sum_{k'>k}f_{lc,k'}\right) +p_u\left(f_{lc,k}\sum_{k'<k}f_{rc,k'}+f_{rc,k}\sum_{k'<k}f_{lc,k'}\right) \]\[f_{u,k}=f_{lc,k}\left((1-p_u)\sum_{k'>k}f_{rc,k'}+p_u\sum_{k'<k}f_{rc,k'}\right)+f_{rc,k}\left((1-p_{u})\sum_{k'>k}f_{lc,k'}+p_u\sum_{k'<k}f_{lc,k'}\right) \]可以考虑线段树合并。
当合并到一个节点为空时，不妨设 \(rc\) 的线段树为空。
设当前线段树区间为 \([l,r]\) 可以发现合并后的值只与 \(lc\) 这棵线段树的值和 \(rc\) 这棵线段树 \([1,l-1]\) 的和，\([r+1,m]\) 的和有关。
这两个值可以在向下递归的时候算出来。
\(lc\) 为空时同理。
总结
本题暴力dp的部分比较好想，但线段树合并较难想到，需要从线段树合并的条件出发思考本题。
线段树合并时更新信息有两个条件：
- 有一棵线段树为空。
- 节点为叶子节点。
回到本题，我们可以发现dp的式子在这两个条件下都较好维护，因此本题可以使用线段树合并。
进一步思考，我们还可以发现，“每个结点的权值互不相同”这个条件是没有用的，就算权值相同，也可以线段树合并。
代码
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int maxn = 3e5 + 5, mod = 998244353;
int n, ch[maxn][2], p[maxn], w[maxn], deg[maxn], a[maxn], m;
#define lc(x) (t[x].lc)
#define rc(x) (t[x].rc)
int root[maxn], cnt;
struct SGT {
int lc, rc, sum, mul;
SGT() { lc = sum = 0; mul = 1; }
} t[maxn * 32];
void push_up(int x) {
t[x].sum = (t[lc(x)].sum + t[rc(x)].sum) % mod;
}
void push_mul(int x, int v) {
t[x].mul = 1ll * t[x].mul * v % mod;
t[x].sum = 1ll * t[x].sum * v % mod;
}
void push_down(int x) {
if(t[x].mul != 1) {
if(lc(x)) push_mul(lc(x), t[x].mul);
if(rc(x)) push_mul(rc(x), t[x].mul);
t[x].mul = 1;
}
}
void modify(int &x, int l, int r, int p, int v) {
if(!x) x = ++cnt, t[x].mul = 1;
if(l == r) {
t[x].sum = v;
t[x].mul = 1;
return;
}
int mid = (l + r) >> 1;
if(mid >= p) modify(lc(x), l, mid, p, v);
else modify(rc(x), mid + 1, r, p, v);
push_up(x);
}
int merge(int x, int y, int l, int r, int u, int sumxl, int sumxr, int sumyl, int sumyr) {
if(!x && !y) return 0;
if(!y) {
int v = (1ll * (1 + mod - p[u]) * sumyr % mod + 1ll * p[u] * sumyl % mod) % mod;
push_mul(x, v);
return x;
}
if(!x) {
int v = (1ll * (1 + mod - p[u]) * sumxr % mod + 1ll * p[u] * sumxl % mod) % mod;
push_mul(y, v);
return y;
}
push_down(x); push_down(y);
int mid = (l + r) >> 1, s1 = t[lc(x)].sum, s2 = t[rc(x)].sum, s3 = t[lc(y)].sum, s4 = t[rc(y)].sum;
lc(x) = merge(lc(x), lc(y), l, mid, u, sumxl, (sumxr + s2) % mod, sumyl, (sumyr + s4) % mod);
rc(x) = merge(rc(x), rc(y), mid + 1, r, u, (sumxl + s1) % mod, sumxr, (sumyl + s3) % mod, sumyr);
push_up(x);
return x;
}
int query(int x, int l, int r, int p) {
if(!x) return 0;
if(l == r) return t[x].sum;
push_down(x); int mid = (l + r) >> 1;
if(mid >= p) return query(lc(x), l, mid, p);
else return query(rc(x), mid + 1, r, p);
}
#undef lc
#undef rc
int ksm(int x, int y) {
int res = 1;
while(y) {
if(y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod, y >>= 1;
}
return res;
}
void dfs(int u) {
if(deg[u] == 0) {
int k = lower_bound(a + 1, a + 1 + m, w[u]) - a;
modify(root[u], 1, m, k, 1);
return;
}
if(deg[u] == 1) {
if(ch[u][0]) dfs(ch[u][0]), root[u] = root[ch[u][0]];
if(ch[u][1]) dfs(ch[u][1]), root[u] = root[ch[u][1]];
return;
}
dfs(ch[u][0]); dfs(ch[u][1]);
root[u] = merge(root[ch[u][0]], root[ch[u][1]], 1, m, u, 0, 0, 0, 0);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1, fa; i <= n; i++) {
cin >> fa;
if(!ch[fa][0]) ch[fa][0] = i;
else ch[fa][1] = i;
deg[fa]++;
}
for(int i = 1, x, fm = ksm(10000, mod - 2); i <= n; i++) {
cin >> x;
if(deg[i] == 0) w[i] = x, a[++m] = x;
else p[i] = 1ll * x * fm % mod;
}
sort(a + 1, a + 1 + m);
dfs(1);
int ans = 0;
for(int i = 1; i <= m; i++) {
int pp = query(1, 1, m, i);
ans = (ans + 1ll * i * a[i] % mod * pp % mod * pp % mod) % mod;
}
cout << ans << '\n';
return 0;
}