萌新刚学 OI 1ms，求调线段树合并模板

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define p_q priority_queue
#define pb push_back
#define mk make_pair
#define pii pair<ll,ll> 
#define ve vector
#define endl '\n'
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
namespace cute_fzj_kuai_ruarua{
	const ll mod=998244353;
	ve<int>tr[300005];
	int n;
	ll p[300005];
	ll ksm(ll a,ll b){
		ll fac=1;
		while(b){
			if(b&1) fac=fac*a%mod;
			a=a*a%mod;
			b>>=1;
		}
		return fac;
	}
	ll val[300005],cnt=0;
	int rt[300005],tot=0;
	ll tag[10000005],sum[10000005];
	int ls[10000005],rs[10000005];
#define mid ((l+r)/2)
	void pushup(int x){
		sum[x]=sum[ls[x]]+sum[rs[x]];
		sum[x]%=mod;
	}
	void push_down(int x,ll k){
		if(!x) return ;
		sum[x]=sum[x]*k%mod;
		tag[x]=tag[x]*k%mod;
	}
	void pushdown(int x){
		if(tag[x]!=1){
			push_down(ls[x],tag[x]);
			push_down(rs[x],tag[x]);
			tag[x]=1;
		}
	}
	void update(int &x,int l,int r,int X){
		if(!x){
			x=++tot;
			tag[x]=1;
		}
		if(l==r){
			sum[x]=1;
			return ;
		}
		pushdown(x);
		if(X<=mid) update(ls[x],l,mid,X);
		else update(rs[x],mid+1,r,X);
		pushup(x);
	}
	int merge(int x,int y,int l,int r,ll suml1,ll suml2,ll sumr1,ll sumr2,ll val1,ll val2){
		if(!x&&!y) return 0;
		int now=++tot;
		tag[now]=1;
		pushdown(y);
		pushdown(x);
		if(!y){
			sum[now]=sum[x];
			push_down(now,(val1*sumr1%mod+val2*sumr2%mod)%mod);
			return now;
		}
		if(!x){
			sum[now]=sum[y];
			push_down(now,(val1*suml1%mod+val2*suml2%mod)%mod);
			return now;
		}
		if(l==r){
			sum[now]=(sum[x]*(val1*sumr1%mod+val2*sumr2%mod)%mod+sum[y]*(val1*suml1%mod+val2*suml2%mod)%mod)%mod;
			return now;
		}
		ll sumll=sum[ls[x]],sumlr=sum[rs[x]];
		ll sumrl=sum[ls[y]],sumrr=sum[rs[y]];
		ls[now]=merge(ls[x],ls[y],l,mid,suml1,(suml2+sumlr)%mod,sumr1,(sumr2+sumrr)%mod,val1,val2);
		rs[now]=merge(rs[x],rs[y],mid+1,r,(suml1+sumll)%mod,suml2,(sumr1+sumrl)%mod,sumr2,val1,val2);
		pushup(now);
		return now;
	}
	void dfs(int x){
		if(!tr[x].size()){
			update(rt[x],1,cnt,p[x]);
			return ;
		}
		if(tr[x].size()==1){
			dfs(tr[x][0]);
			rt[x]=rt[tr[x][0]];
			return ;
		}
		int ls=tr[x][0];
		int rs=tr[x][1];
		dfs(ls);
		dfs(rs);
		ll val1=p[x]*ksm(10000,mod-2)%mod;
		ll val2=(10000-p[x])*ksm(10000,mod-2)%mod;
		rt[x]=merge(rt[ls],rt[rs],1,cnt,0,0,0,0,val1,val2);
	}
	ll ans=0;
	void dfss(int x,int l,int r){
		if(l==r){
			ans=(ans+val[l]*l%mod*sum[x]%mod*sum[x]%mod)%mod;
			return ;
		}
		pushdown(x);
		dfss(ls[x],l,mid);
		dfss(rs[x],mid+1,r);
	}
	void main(){
		cin>>n;
		for(int i=1;i<=n;i++){
			int _;
			cin>>_;
			tr[_].pb(i);
		}
		for(int i=1;i<=n;i++) cin>>p[i];
		for(int i=1;i<=n;i++){
			if(!tr[i].size()){
				val[++cnt]=p[i];
			}
		}
		sort(val+1,val+1+cnt);
		cnt=unique(val+1,val+1+cnt)-val-1;
		for(int i=1;i<=n;i++){
			if(!tr[i].size()){
				p[i]=lower_bound(val+1,val+1+cnt,p[i])-val;
			}
		}
		dfs(1);
		dfss(rt[1],1,cnt);
		cout<<ans;
	}
}
using namespace cute_fzj_kuai_ruarua;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cute_fzj_kuai_ruarua::main();
	return 0;
}