Minimax: Line segment tree merging optimization dp good question.
tree shape dp
Because we require the probability of occurrence of each value, first we can think of a very violent dp formula.
definition\(dp_{i,j}\)Indicates on the node\(i\)When weight\(j\)The probability of occurrence,\(l\)Represent the left son,\(r\)To indicate the right son, there will be the following transfers:
- when\(j\)When in the left son,\(dp_{i,j}\gets dp_{l,j}\times(p_i\times\sum_{k=1}^{j-1}dp_{r,k}+(1-p_i)\times\sum_{k=j+1}^{V}dp_{r,k})\), if you understand it, it is to discuss whether the father nodes choose the big one or the small one.
- when\(j\)When in the right son,\(dp_{i,j}\gets dp_{r,j}\times(p_i\times\sum_{k=1}^{j-1}dp_{l,k}+(1-p_i)\times\sum_{k=j+1}^Vdp_{l,k})\)。
Just transfer directly, time complexity\(O(nV)\)。
Line segment tree merging optimization
Obviously the original time complexity will explode, but we foundAt the beginning of each node, there is only one dp position that has a value., so we consider optimizing this dp using this segment tree merging of evenly amortized complexity.
Because prefix and suffix sum are required when transferring dp, we record nodes when combining\(x,y\)prefix and\(px,py\)With suffix and\(sx,sy\)And the probability of the father node\(p\)。
Let’s sort out the process of merge:
- Enter the node\(x,y\)。
- if\(x,y\)If one of them is an empty tree, it means that the dp value can be directly updated.
- like\(x\)It is an empty tree, corresponding to the above\(j\)In the right son's transfer method, then we\(y\)The dp values in the entire subtree are multiplied by\((p\times\sum_{k=1}^{j-1}dp_{l,k}+(1-p)\times\sum_{k=j+1}^Vdp_{l,k})=(p\times px+(1-p)\times sx)\)Just do it. This can be done by using lazy marks to implement interval multiplication.
- like\(y\)It is an empty tree, corresponding to the above\(j\)In the way of transfer in the left son, then we\(x\)The dp values in the entire subtree are multiplied by\((p\times\sum_{k=1}^{j-1}dp_{r,k}+(1-p)\times\sum_{k=j+1}^Vdp_{r,k})=(p\times py+(1-p)\times sy)\)Just do it. This can be done by using lazy marks to implement interval multiplication.
- Otherwise, it means you need to merge recursively. Remember to update when recursively holding your son.\(sx,sy,px,py\)value.
- Finally, add up the dp values of the left and right sons to the dp values of this interval.
Time complexity\(O(n\log n)\)。
Code
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int N=300005;
const ll mod=998244353;
int n,fa[N],m=0,b[N],son[N][2],cd[N],p[N],ans[N];
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)res=(res*a)%mod;
b>>=1;
a=(a*a)%mod;
}
return res;
}
int getrk(int x)
{
return (lower_bound(b+1,b+m+1,x)-b);
}
struct Node{
int ls,rs;
ll dp,tag=1;
};
struct Segtree{
Node tr[20*N];
int root[N],tot=0;
void pushup(int p)
{
tr[p].dp=(tr[lc(p)].dp+tr[rc(p)].dp)%mod;
}
void pushdown(int p)
{
if(tr[p].tag!=1)
{
tr[lc(p)].tag=(tr[lc(p)].tag*tr[p].tag)%mod;
tr[rc(p)].tag=(tr[rc(p)].tag*tr[p].tag)%mod;
tr[lc(p)].dp=(tr[lc(p)].dp*tr[p].tag)%mod;
tr[rc(p)].dp=(tr[rc(p)].dp*tr[p].tag)%mod;
}
tr[p].tag=1;
}
void modify(int p,int v)
{
tr[p].dp=(tr[p].dp*1ll*v)%mod;
tr[p].tag=(tr[p].tag*1ll*v)%mod;
}
void update(int &u,int ln,int rn,int x,ll k)
{
if(u==0)u=++tot;
if(ln==rn){tr[u].dp+=k;return;}
int mid=(ln+rn)>>1;
if(x<=mid)update(lc(u),ln,mid,x,k);
else update(rc(u),mid+1,rn,x,k);
pushup(u);
}
int merge(int x,int y,int px,int py,int sx,int sy,int p)
{
if(x==0&&y==0)return 0;
if(x==0)
{
modify(y,(1ll*p*px%mod+1ll*((1-p)%mod+mod)%mod*sx)%mod);
return y;
}
if(y==0)
{
modify(x,(1ll*p*py%mod+1ll*((1-p)%mod+mod)%mod*sy)%mod);
return x;
}
pushdown(x);pushdown(y);
int lx=tr[lc(x)].dp,rx=tr[rc(x)].dp,ly=tr[lc(y)].dp,ry=tr[rc(y)].dp;
tr[x].ls=merge(lc(x),lc(y),px,py,(sx+rx)%mod,(sy+ry)%mod,p);
tr[x].rs=merge(rc(x),rc(y),(px+lx)%mod,(py+ly)%mod,sx,sy,p);
pushup(x);
return x;
}
void query(int u,int ln,int rn)
{
if(ln==rn){ans[ln]=tr[u].dp;return;}
int mid=(ln+rn)>>1;
pushdown(u);
query(lc(u),ln,mid);
query(rc(u),mid+1,rn);
}
}tr1;
void dfs1(int u)
{
if(son[u][0]==0)
{
([u],1,m,getrk(p[u]),1);
return;
}
if(son[u][1]==0)
{
dfs1(son[u][0]);
[u]=[son[u][0]];
return;
}
dfs1(son[u][0]);
dfs1(son[u][1]);
[u]=([son[u][0]],[son[u][1]],0,0,0,0,p[u]);
}
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
ios::sync_with_stdio(0);
(0);
(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>fa[i];
for(int i=1;i<=n;i++)
{
son[fa[i]][cd[fa[i]]]=i;
cd[fa[i]]++;
}
for(int i=1;i<=n;i++)
{
cin>>p[i];
if(cd[i])p[i]=p[i]*1ll*qpow(10000,mod-2)%mod;
else b[++m]=p[i];
}
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
dfs1(1);
([1],1,m);
ll res=0;
for(int i=1;i<=m;i++)res=(res+1ll*i*b[i]%mod*ans[i]%mod*ans[i]%mod)%mod;
cout<<res;
return 0;
}