这道题挺显然的吧
我们设(dp_{x,k})表示(x)这个点的权值为(k)的概率是多少
我们注意到到题目里保证了权值不重复
于是我们可以把转移写成
[dp_{x,k}=(p_xsum_{i=1}^{k-1}dp_{ls,i}+(1-p_x)sum_{i=k+1}^mdp_{ls,i})dp_{rs,k}
]
这是(k)来自右儿子的情况，左儿子同理
我们发现我们这个柿子完全可以直接线段树合并来优化，因为我们在发现有一棵线段树为空的时候，对于另一边的线段树来说，前面的那个转移的概率是不变的，直接打一个区间乘法标记就好了
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=3e5+5;
const int M=maxn*45;
const int mod=998244353;
const int Inv=796898467;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int l[M],r[M],d[M],tag[M];
int val[maxn],fa[maxn],p[maxn],ls[maxn],rt[maxn],rs[maxn],c[maxn];
int n,num,m,P,O,cnt;
inline void add(int x,int y) {
if(!ls[x]) {ls[x]=y;return;}
rs[x]=y;
}
inline void pushup(int i) {
d[i]=(d[l[i]]+d[r[i]])%mod;
}
int change(int now,int x,int y,int pos) {
if(!now) now=++cnt,tag[now]=1;
if(x==y) {d[now]=1;return now;}
int mid=x+y>>1;
if(pos<=mid) l[now]=change(l[now],x,mid,pos);
else r[now]=change(r[now],mid+1,y,pos);
pushup(now);
return now;
}
inline void pushdown(int i) {
if(tag[i]==1) return;
tag[l[i]]=1ll*tag[l[i]]*tag[i]%mod;
tag[r[i]]=1ll*tag[r[i]]*tag[i]%mod;
d[l[i]]=1ll*d[l[i]]*tag[i]%mod;
d[r[i]]=1ll*d[r[i]]*tag[i]%mod;
tag[i]=1;
}
int merge(int a,int b,int x,int y,int lsum,int rsum) {
if(!a&&!b) return 0;
if(a) pushdown(a);
if(b) pushdown(b);
if(!b) {
int v=(1ll*P*rsum%mod+1ll*O*((1-rsum+mod)%mod)%mod)%mod;
tag[a]=1ll*tag[a]*v%mod;
d[a]=1ll*d[a]*v%mod;
return a;
}
if(!a) {
int v=(1ll*P*lsum%mod+1ll*O*((1-lsum+mod)%mod)%mod)%mod;
d[b]=1ll*d[b]*v%mod;
tag[b]=1ll*tag[b]*v%mod;
return b;
}
int mid=x+y>>1;
r[a]=merge(r[a],r[b],mid+1,y,(lsum+d[l[a]])%mod,(rsum+d[l[b]])%mod);
l[a]=merge(l[a],l[b],x,mid,lsum,rsum);
pushup(a);return a;
}
void dfs(int x) {
if(!ls[x]&&!rs[x]) return;
dfs(ls[x]);
if(!rs[x]) {rt[x]=rt[ls[x]];return;}
dfs(rs[x]);
P=p[x],O=(1-p[x]+mod)%mod;
rt[x]=merge(rt[ls[x]],rt[rs[x]],1,m,0,0);
}
inline int find(int x) {
int le=1,ri=m;
while(le<=ri) {
int mid=le+ri>>1;
if(c[mid]==x) return mid;
if(c[mid]>x) ri=mid-1;
else le=mid+1;
}
return 0;
}
int query(int now,int x,int y) {
if(!now) return now;
if(x==y) return ++num,1ll*num*c[num]%mod*d[now]%mod*d[now]%mod;
pushdown(now);
int mid=x+y>>1;
return (query(l[now],x,mid)+query(r[now],mid+1,y))%mod;
}
int main() {
n=read();
for(re int i=1;i<=n;i++) fa[i]=read();
for(re int i=2;i<=n;i++) add(fa[i],i);
for(re int i=1;i<=n;i++) {
int t=read();
if(!ls[i]) val[i]=t,c[++m]=t;
else p[i]=1ll*t*Inv%mod;
}
std::sort(c+1,c+m+1);
for(re int i=1;i<=n;i++) {
if(!val[i]) continue;
val[i]=find(val[i]);
rt[i]=change(rt[i],1,m,val[i]);
}
dfs(1);
printf("%d",query(rt[1],1,m));
return 0;
}