Solution
开始做完全没想到是线段树合并QAQ、
朴素的做法是直接树形dp。设(f[u][x])表示在u点权值取到x的概率。
有转移:
如果x在左子树 (f[u][x]=f[ls][x] imes sumlimits_{yin T_{rs},y<x}f[rs][y] imes p[u]+f[ls][x] imes sumlimits_{yin T_{rs},y>x}f[rs][y] imes (1-p[u]))
就是以x作为最大值还是最小值出现来转移，x在右子树同理。
然鹅暴力做状态都存不下。考虑对每个节点开一棵权值线段树（主席树形式）这样空间复杂度( ext O(nlogn))。
维护x的信息相当于合并x两儿子的线段树。
这时会发现枚举每个元素进行转移还是很假，考虑利用类似cdq分治的思想进行转移，分治前计算好右树对左树的贡献（对于左树每个点来说，右树贡献相同），和左树对右树的贡献，一直递归到叶节点，把贡献加进去就好了。
另外虽说主席树空间复杂度是( ext O(nlogn))，但是还是稍微开大一点，一般开N的40~50倍就差不多。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){//be careful for long long!
register int x=0,f=1;register char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
return f?x:-x;
}
const int N=3e5+10,mod=998244353;;
int n,tr[N*50],ls[N*50],rs[N*50],cnt,p[N],rt[N],tag[N*50],w[N],maxn;
inline int power(int base,int n){int ans=1;for(;n;n>>=1,base=1ll*base*base%mod)if(n&1)ans=1ll*ans*base%mod;return ans;}
int tot,ans,inv=power(10000,mod-2);
vector<int> E[N];
inline void update(int p){tr[p]=(tr[ls[p]]+tr[rs[p]])%mod;}
inline void pushtag(int p,int v){tr[p]=1ll*tr[p]*v%mod,tag[p]=1ll*tag[p]*v%mod;}
inline void pushdown(int p){
if(tag[p]==1)return;
pushtag(ls[p],tag[p]),pushtag(rs[p],tag[p]);
tag[p]=1;
}
inline void insert(int &p,int l,int r,int pos){
if(!p)p=++cnt;tag[p]=tr[p]=1;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)insert(ls[p],l,mid,pos);
else insert(rs[p],mid+1,r,pos);
update(p);
}
inline int merge(int x,int y,int px,int py,int p){
if(!(x+y))return 0;
if(!x){pushtag(y,py);return y;}
if(!y){pushtag(x,px);return x;}
int lx,rx,ly,ry;
pushdown(x),pushdown(y);
lx=(px+1ll*tr[rs[y]]*(1-p+mod)%mod)%mod;
ly=(py+1ll*tr[rs[x]]*(1-p+mod)%mod)%mod;
rx=(px+1ll*tr[ls[y]]*p%mod)%mod;
ry=(py+1ll*tr[ls[x]]*p%mod)%mod;
ls[x]=merge(ls[x],ls[y],lx,ly,p);
rs[x]=merge(rs[x],rs[y],rx,ry,p);
update(x);
return x;
}
inline void dfs(int nw){
for(int i=0;i<(int)E[nw].size();++i)
dfs(E[nw][i]);
if(!E[nw].size())insert(rt[nw],1,maxn,w[nw]);
else if(E[nw].size()==1)rt[nw]=rt[E[nw][0]];
else rt[nw]=merge(rt[E[nw][0]],rt[E[nw][1]],0,0,(int)(1ll*w[nw]*inv%mod));
}
inline void cal(int p,int l=1,int r=maxn){
if(!p)return;
if(l==r){
ans=(ans+1ll*tr[p]*tr[p]%mod*l%mod*(++tot)%mod)%mod;
return;
}
pushdown(p);
int mid=(l+r)>>1;
cal(ls[p],l,mid),cal(rs[p],mid+1,r);
}
int main(){
n=read();
for(int i=1;i<=n;++i)E[read()].push_back(i);
for(int i=1;i<=n;++i)maxn=max(maxn,w[i]=read());
dfs(1);cal(rt[1]);
printf("%d
",ans);
return 0;
}