题意

题意

题解

当时在考场上很傻逼，只会$O(n^2)$的做法。。
然后可能是大概听过一点做法吧。。
反正再一次做这题的时候就知道了$(nlog^2n)$的做法
大概就是维护两个线段树
然后合并的时候就启发式合并。。
暴力遍历小的一个，容易发现，合并的时候，信息变的肯定是连续的两端
然后就可以做到两个$log$了
听说考试的时候，有人用两个log过了，但羊说他过不去。。
但是有更优秀的方法
就是线段树合并
文化课选手并没有想这个，但其实也很简单
你每一次合并的时候维护两个东西
一个是x这个子树当前的概率，一个是y这个子树当前的概率
然后直接线段树合并就可以了
感觉我讲得不清不楚。。但是(⊙o⊙)…，大家往线段树合并的方向想就好了。。
然后一开始又犯了递归的常见错误而调了很久
1.当你有全局变量的时候一定要注意
2.当你要用一个信息，但是这个信息可能在以后被修改，那么一定要先拿下来
大概就这样了
不知道为什么log上过不去，我把包下下来，自己测了一下，都过了

因为我机子比较慢，因此时间开大了一点

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=300005*20;
const LL MOD=998244353;
LL son[300005][2];
LL n;
LL w[N],b[N],tot=0;
LL inv;
LL pow (LL x,LL y)
{if (y==1) return x;LL lalal=pow(x,y>>1);lalal=lalal*lalal%MOD;if (y&1) lalal=lalal*x%MOD;return lalal;
}
LL s1[N],s2[N],num=0;
LL lzy[N],p;
LL c[N];//这里的概率
LL add (LL l,LL r,LL x)
{LL now=++num;lzy[now]=c[now]=1;if (l==r) return now;LL mid=(l+r)>>1;if (x<=mid) s1[now]=add(l,mid,x);else s2[now]=add(mid+1,r,x);return now;
}
void change (LL now,LL cc)
{lzy[now]=lzy[now]*cc%MOD;c[now]=c[now]*cc%MOD;return ;
}
void push_down (LL now)
{LL lalal=lzy[now];lzy[now]=1;c[s1[now]]=c[s1[now]]*lalal%MOD;        lzy[s1[now]]=lzy[s1[now]]*lalal%MOD;c[s2[now]]=c[s2[now]]*lalal%MOD;        lzy[s2[now]]=lzy[s2[now]]*lalal%MOD;
}
LL Merge (LL rt1,LL rt2,LL x1,LL x2)
{if (rt1==0) {change(rt2,x2);return rt2;}if (rt2==0) {change(rt1,x1);return rt1;}//printf("%lld %lld %lld %lld\n",rt1,rt2,x1,x2);push_down(rt1);push_down(rt2);LL A=c[s2[rt2]],B=c[s2[rt1]],C=c[s1[rt2]],D=c[s1[rt1]];//printf("%lld %lld %lld %lld p:%lld\n",A,B,C,D,p);s1[rt1]=Merge(s1[rt1],s1[rt2],(x1+(1LL-p)*A%MOD)%MOD,(x2+(1LL-p)*B%MOD)%MOD);//printf("hehe\n");s2[rt1]=Merge(s2[rt1],s2[rt2],(x1+p*C%MOD)%MOD,(x2+p*D%MOD)%MOD);c[rt1]=(c[s1[rt1]]+c[s2[rt1]])%MOD;return rt1;
}
LL solve (LL x)//要处理哪一个节点
{
//  printf("now:%d\n",x);if (son[x][0]==0)//如果这就是一个叶子节点了{//printf("%lld %lld\n",x,(LL)(lower_bound(b+1,b+tot+1,w[x])-b));return add(1,tot,(LL)(lower_bound(b+1,b+tot+1,w[x])-b));}if (son[x][1]==0)   return solve(son[x][0]);int ss1=solve(son[x][0]),ss2=solve(son[x][1]);p=w[x]*inv%MOD;return Merge(ss1,ss2,0,0);
}
LL ans=0;
void dfs (LL now,LL l,LL r)
{//printf("%lld %lld %lld\n",l,r,(c[now]+MOD)%MOD);if (l==r){//  printf("%lld %lld %lld\n",l,b[l],c[now]);ans=(ans+l*b[l]%MOD*c[now]%MOD*c[now]%MOD)%MOD;return ;}push_down (now);LL mid=(l+r)>>1;dfs(s1[now],l,mid);dfs(s2[now],mid+1,r);
}
int main()
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);memset(son,0,sizeof(son));inv=pow(10000,MOD-2);scanf("%lld",&n);for (LL u=1;u<=n;u++){LL x;scanf("%lld",&x);if (son[x][0]==0) son[x][0]=u;else son[x][1]=u;}for (LL u=1;u<=n;u++){scanf("%lld",&w[u]);if (son[u][0]==0) b[++tot]=w[u];}sort(b+1,b+1+tot);dfs(solve(1),1,tot);ans=(ans+MOD)%MOD;printf("%lld\n",ans);return 0;
}