这道题挺显然的吧
我们设\(dp_{x,k}\)表示\(x\)这个点的权值为\(k\)的概率是多少
我们注意到到题目里保证了权值不重复
于是我们可以把转移写成
\[dp_{x,k}=(p_x\sum_{i=1}^{k-1}dp_{ls,i}+(1-p_x)\sum_{i=k+1}^mdp_{ls,i})dp_{rs,k}\]
这是\(k\)来自右儿子的情况，左儿子同理
我们发现我们这个柿子完全可以直接线段树合并来优化，因为我们在发现有一棵线段树为空的时候，对于另一边的线段树来说，前面的那个转移的概率是不变的，直接打一个区间乘法标记就好了
代码
#include#include #include #include #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;}