一个节点 $i$ 的权值有 $p_i$ 的可能是儿子节点权值最大值,$1-p_i$ 的可能是儿子节点权值最小值(至多两个儿子),假设根节点(1)权值有 $m$ 种可能,第 $i$ 小的为 $v_i$ ,概率为 $d_i$ ,求 $\sum_{i=1}^{m}i\times v_i\times d_i^2\ mod\ 998244353$ 。
看起来是一道正常的概率题目,但是答案式子很奇怪啊?所以我们干脆想办法求出所有可能的权值。
然后你就会发现这tm变成了数据结构题,对每个节点开一棵权值线段树(或者平衡树)储存每个权值的概率,然后启发式合并。但这样肯定爆空间啊,有两个选择:主席树、动态开点。能用动态开点还是动态开点好。
怎么合并?设目前的节点为 $x$ ,我们把小的树记为 $L$ ,大的记为 $R$ ,那么:
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000,maxt=2e7,MOD=998244353;
int n,p[maxn+5],son[maxn+5][2],tem[maxn+5],ro[maxn+5],si[maxn+5],ans;
int len,sum[maxt+5],ls[maxt+5],rs[maxt+5],tag[maxt+5];
int INV,K[maxn+5],val[maxn+5],now[maxn+5],pre[maxn+5],suf[maxn+5];
#define Add(x,y) (son[x][0]?son[x][1]=y:son[x][0]=y)
inline int Find(int x){
for (int L=1,R=tem[0],mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
if (x==tem[mid=L+(R-L>>1)]) return mid; else x<tem[mid]?R=mid-1:L=mid+1;
}
#define newnode (tag[++len]=1,len)
#define Addtag(p,k) sum[p]=(LL)sum[p]*(k)%MOD,tag[p]=(LL)tag[p]*(k)%MOD
inline void Pushdown(int p){
if (tag[p]==1) return;if (!ls[p]) ls[p]=newnode;if (!rs[p]) rs[p]=newnode;
Addtag(ls[p],tag[p]);Addtag(rs[p],tag[p]);tag[p]=1;
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
void Update(int &p,int pos,int k,int l=1,int r=tem[0]){
if (!p) p=newnode;if (l==r) {sum[p]=k;return;}Pushdown(p);int mid=l+(r-l>>1);
if (pos<=mid) Update(ls[p],pos,k,l,mid); else Update(rs[p],pos,k,mid+1,r);
AMOD(sum[p]=sum[ls[p]],sum[rs[p]]);
}
void Multi(int &p,int L,int R,int k,int l=1,int r=tem[0]){
if (R<l||r<L) return;if (!p) p=newnode;if (L<=l&&r<=R) {Addtag(p,k);return;}
Pushdown(p);int mid=l+(r-l>>1);Multi(ls[p],L,R,k,l,mid);Multi(rs[p],L,R,k,mid+1,r);
AMOD(sum[p]=sum[ls[p]],sum[rs[p]]);
}
#define emp(p) (!(p)||!sum[p]&&!ls[p]&&!rs[p])
int Ask(int p,int L,int R,int l=1,int r=tem[0]){
if (R<l||r<L||emp(p)) return 0; if (L<=l&&r<=R) return sum[p];Pushdown(p);
int mid=l+(r-l>>1);return (Ask(ls[p],L,R,l,mid)+Ask(rs[p],L,R,mid+1,r))%MOD;
}
void gettree(int p,int l=1,int r=tem[0]){
if (emp(p)) return;if (l==r) {K[++K[0]]=l;val[K[0]]=sum[p];return;}
Pushdown(p);int mid=l+(r-l>>1);gettree(ls[p],l,mid);gettree(rs[p],mid+1,r);
}
#define Sum(i,j) ((((LL)p[x]*pre[i]%MOD+(LL)(MOD+1-p[x])*suf[j])%MOD)%MOD)
void getleaf(int x){
int L=son[x][0],R=son[x][1];if (!L) {tem[++tem[0]]=p[x];return;}
getleaf(L);if (R) getleaf(R);
}
void Dfs(int x){
int L=son[x][0],R=son[x][1];if (!L) return si[x]=1,Update(ro[x],Find(p[x]),1);
if (L&&!R) {Dfs(L);ro[x]=ro[L];si[x]=si[L];return;}
Dfs(L);Dfs(R);si[x]=si[L]+si[R];p[x]=(LL)p[x]*INV%MOD;
if (si[L]>si[R]) swap(L,R);ro[x]=ro[R];K[0]=0;gettree(ro[L]);
for (int i=1;i<=K[0];i++){
now[i]=(LL)p[x]*val[i]%MOD*Ask(ro[x],1,K[i]-1)%MOD;
AMOD(now[i],(LL)(MOD+1-p[x])*val[i]%MOD*Ask(ro[x],K[i]+1,tem[0])%MOD);
}
for (int i=1;i<=K[0];i++) Update(ro[x],K[i],now[i]);
pre[0]=0;for (int i=1;i<=K[0];i++) AMOD(pre[i]=pre[i-1],val[i]);
suf[K[0]+1]=0;for (int i=K[0];i;i--) AMOD(suf[i]=suf[i+1],val[i]);
Multi(ro[x],1,K[1]-1,Sum(0,1));
for (int i=2;i<=K[0];i++) Multi(ro[x],K[i-1]+1,K[i]-1,Sum(i-1,i));
Multi(ro[x],K[K[0]]+1,tem[0],Sum(K[0],K[0]+1));
}
inline int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=(LL)s*w%MOD;b>>=1;if (b) w=(LL)w*w%MOD;}return s;}
int main(){
freopen("program.in","r",stdin);
freopen("program.out","w",stdout);
scanf("%d%*d",&n);for (int i=2,fa;i<=n;i++) scanf("%d",&fa),Add(fa,i);
for (int i=1;i<=n;i++) scanf("%d",&p[i]);getleaf(1);
sort(tem+1,tem+1+tem[0]);tem[0]=unique(tem+1,tem+1+tem[0])-tem-1;
INV=Pow(10000,MOD-2);Dfs(1);K[0]=0;gettree(ro[1]);
for (int i=1;i<=K[0];i++) AMOD(ans,(LL)i*tem[K[i]]%MOD*val[i]%MOD*val[i]%MOD);
return printf("%d\n",ans),0;
}
alert("手动滑稽")
以及2个log跑3e5好像确实有点卡啊qwq
@panda_2134
好像有一个log的解法……但是我太菜了不会……
@ZigZagK
我写了个和您一样的2个log的,3s TLE