小 C 有一棵 n 个结点的有根树，根是 1 号结点，且每个结点最多有两个子结点。
定义结点 x 的权值为：
1.若 x 没有子结点，那么它的权值会在输入里给出，保证这类点中每个结点的权值互不相同。
2.若 x 有子结点，那么它的权值有 px的概率是它的子结点的权值的最大值，有 1?px的概率是它的子结点的权值的最小值。
现在小 C 想知道，假设 1 号结点的权值有 m 种可能性，权值第 i 小的可能性的权值是 Vi，它的概率为 Di，求：
1 #include<cstdio> 2 #include<algorithm> 3 #define N 300005 4 #define mod 998244353 5 #define inv 796898467 6 #define ll long long 7 using namespace std; 8 int n,m,son[N][2],top; 9 ll b[N],w[N]; 10 ll s[N*50],tag[N*50],ls[N*50],rs[N*50],p; 11 int newtree(int l,int r,int x){ 12 int node=++top; 13 s[node]=tag[node]=1; 14 if(l==r)return node; 15 int mid=(l+r)>>1; 16 if(x<=mid)ls[node]=newtree(l,mid,x); 17 else rs[node]=newtree(mid+1,r,x); 18 return node; 19 } 20 void mul(int x,ll v){s[x]=(s[x]*v)%mod;tag[x]=(tag[x]*v)%mod;} 21 void pushdown(int x){if(tag[x]==1)return;mul(ls[x],tag[x]);mul(rs[x],tag[x]);tag[x]=1;} 22 int merge(int x,int y,ll sx,ll sy){ 23 if(!x){mul(y,sx);return y;} 24 if(!y){mul(x,sy);return x;} 25 pushdown(x),pushdown(y); 26 ll x0=s[ls[x]],x1=s[rs[x]],y0=s[ls[y]],y1=s[rs[y]]; 27 ls[x]=merge(ls[x],ls[y],(sx+(1+mod-p)*x1)%mod,(sy+(1+mod-p)*y1)%mod); 28 rs[x]=merge(rs[x],rs[y],(sx+p*x0)%mod,(sy+p*y0)%mod); 29 s[x]=(s[ls[x]]+s[rs[x]])%mod; 30 return x; 31 } 32 int dfs(int x){ 33 if(!son[x][0])return newtree(1,m,lower_bound(b+1,b+1+m,w[x])-b); 34 int L=dfs(son[x][0]); 35 if(!son[x][1])return L; 36 int R=dfs(son[x][1]); 37 p=(w[x]*inv)%mod; 38 return merge(L,R,0,0); 39 } 40 ll calc(int l,int r,int x){ 41 if(l==r)return (ll)l*b[l]%mod*s[x]%mod*s[x]%mod; 42 pushdown(x); 43 int mid=(l+r)>>1; 44 return (calc(l,mid,ls[x])+calc(mid+1,r,rs[x]))%mod; 45 } 46 int main(){ 47 scanf("%d",&n); 48 for(int i=1,x;i<=n;i++)scanf("%d",&x),son[x][son[x][0]?1:0]=i; 49 for(int i=1;i<=n;i++){ 50 scanf("%lld",&w[i]); 51 if(!son[i][0])b[++m]=w[i]; 52 } 53 sort(b+1,b+1+m); 54 printf("%lld",calc(1,m,dfs(1))); 55 return 0; 56 }
原文：https://www.cnblogs.com/2017SSY/p/10291686.html
