题面
题解
线段树合并吼题啊
合并的时候要记一下$A$点权值小于$l$的概率和$A$点权值大于$r$的概率，对$B$点同样做
时空复杂度$\text O(nlogw)$，$w$为其中权值的最大值
代码
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#define RG register#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);#define clear(x, y) memset(x, y, sizeof(x))inline int read(){int data = 0, w = 1; char ch = getchar();while(ch != '-' && (!isdigit(ch))) ch = getchar();if(ch == '-') w = -1, ch = getchar();while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();return data * w;}const int Mod(998244353), Inv(796898467), maxn(300010), LIM((1 << 30) - 1);inline int Add(int a, int b) { return (a + b) % Mod; }int ans, cnt, son[2][maxn * 20], tag[maxn * 20], P[maxn * 20], cur, root[maxn];inline int newNode(){tag[++cur] = 1; P[cur] = 0;son[0][cur] = son[1][cur] = 0;return cur;}inline void pushup(int x) { P[x] = Add(P[son[0][x]], P[son[1][x]]); }inline void put_tag(int x, int p){if(!x) return;tag[x] = 1ll * tag[x] * p % Mod;P[x] = 1ll * P[x] * p % Mod;}inline void pushdown(int x){put_tag(son[0][x], tag[x]);put_tag(son[1][x], tag[x]);tag[x] = 1;}void calc(int x, int l = 0, int r = LIM){if(!x) return;if(l == r){++cnt; ans = Add(ans, 1ll * cnt * P[x] % Mod * P[x] % Mod * l % Mod);return;}pushdown(x);int mid = (l + r) >> 1;calc(son[0][x], l, mid);calc(son[1][x], mid + 1, r);}void insert(int &x, int id, int l = 0, int r = LIM){if(!x) x = newNode();tag[x] = P[x] = 1;if(l == r) return;int mid = (l + r) >> 1;if(id <= mid) insert(son[0][x], id, l, mid);else insert(son[1][x], id, mid + 1, r);}int S[2][maxn], tot[maxn], W[maxn], n;int merge(int a, int b, int pa, int pb, int pmax){if(!a && !b) return 0;if(!a) return put_tag(b, pa), b;if(!b) return put_tag(a, pb), a;pushdown(a), pushdown(b);int pal = Add(pa, 1ll * P[son[1][a]] * Add(Mod - pmax, 1) % Mod),pbl = Add(pb, 1ll * P[son[1][b]] * Add(Mod - pmax, 1) % Mod),par = Add(pa, 1ll * P[son[0][a]] * pmax % Mod),pbr = Add(pb, 1ll * P[son[0][b]] * pmax % Mod);son[0][a] = merge(son[0][a], son[0][b], pal, pbl, pmax);son[1][a] = merge(son[1][a], son[1][b], par, pbr, pmax);return pushup(a), a;}void dfs(int x){if(!tot[x]) return (void) (insert(root[x], W[x]));W[x] = 1ll * W[x] * Inv % Mod;for(RG int i = 0; i < tot[x]; i++) dfs(S[i][x]);if(tot[x] == 1) root[x] = root[S[0][x]];else root[x] = merge(root[S[0][x]], root[S[1][x]], 0, 0, W[x]);}int main(){#ifndef ONLINE_JUDGEfile(cpp);#endifn = read();for(RG int i = 1, fa; i <= n; i++)fa = read(), S[tot[fa]++][fa] = i;for(RG int i = 1; i <= n; i++) W[i] = read();dfs(1); calc(root[1]); printf("%d\n", ans);return 0;}
