首先我们可以想到一个显而易见的 $\rm{DP}$ ：
设 $dp_{u,w}$ 表示点 $u$ 的权值为 $w$ 的概率，考虑转移：
$$
dp_{u,w}=dp_{a,w}\times\left(p_u\sum_{w'<w}dp_{b,w’}+(1-p_{u})\sum_{w’>w}dp_{b,w’}\right)
$$
其中 $a$ 表示权值来源的那个子树，$b$ 表示另一个子树，容易发现这样 $\rm{DP}$ 的复杂度是 $O(n^2)$ 的，可以得到 $40pts$ 。
然后我们需要优化，考虑线段树合并。
每一次将一个节点两个儿子的线段树进行合并，那么到达每一个节点就有三种情况：
- 两个儿子的线段树都没有该节点：
也就是说无论两个儿子哪个是 $a$ ，$dp_{a,w},w\in[l,r]$ 都必然为 $0$ ，直接返回即可。
-
两个儿子的线段树都有该节点：
继续往下更新即可。
-
两个儿子的线段树一个有该节点，另一个没有：
假设有该节点的儿子为 $a$ ，另一个儿子为 $b$ ，可以发现我们只需要计算 $a$ 带来的贡献，由于这一段值域区间都没有概率被 $b$ 选中，所以对于这一段值域区间的所有 $dp_{a,w}$ 乘上的都是一个数，打个乘法标记就好了。
线段树合并的时候需要顺带维护一下 $\sum_{w’>w}dp_{b,w’}$ ，这样在计算贡献的时候 $dp_{a,w}$ 乘上的数就是 ：
$$
p_u(1-\sum_{w’>w}dp_{b,w’})+(1-p_{u})\sum_{w’>w}dp_{b,w’}
$$
直接计算，肥肠方便。
Code：
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=3e5+5;
const int LogN=45;
const ll mod=998244353;
int n,cnt,fa[N];
ll v[N],p[N],H[N],ans;
vector <int> son[N];
inline ll modpow(ll x,ll y) {
ll res=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
return res;
}
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
namespace Segment_Tree {
#define mid ((l+r)>>1)
int rt[N],tot;
struct Node {int lc,rc;ll sum,tag;}t[N*LogN];
ll res1,res2,tmp1,tmp2;
inline void update(int&x,int l,int r,int pos,ll val) {
if(!x) x=++tot,t[x].tag=1;
if(l==r) {t[x].sum=val;return;}
(pos<=mid)?update(t[x].lc,l,mid,pos,val):update(t[x].rc,mid+1,r,pos,val);
t[x].sum=(t[t[x].lc].sum+t[t[x].rc].sum)%mod;
}
inline void pushdown(int x) {
if(t[x].lc) (t[t[x].lc].sum*=t[x].tag)%=mod,(t[t[x].lc].tag*=t[x].tag)%=mod;
if(t[x].rc) (t[t[x].rc].sum*=t[x].tag)%=mod,(t[t[x].rc].tag*=t[x].tag)%=mod;
t[x].tag=0;
}
/*res1 :: l(update to)u,l>r*/
/*res2 :: r(update to)u,r>l*/
inline void merge(int&x,int a,int b,int l,int r) {
if(!a&&!b) return;
if(!x) x=++tot,t[x].tag=1;
pushdown(a),pushdown(b);
if(!a||!b) {
if(!b) {
t[x].sum=t[a].sum*(tmp2*res2%mod+tmp1*(1-res2+mod)%mod)%mod;
t[x].tag=(tmp2*res2%mod+tmp1*(1-res2+mod)%mod)%mod;
t[x].sum%=mod,t[x].tag%=mod,t[x].lc=t[a].lc,t[x].rc=t[a].rc;
} else {
t[x].sum=t[b].sum*(tmp2*res1%mod+tmp1*(1-res1+mod)%mod)%mod;
t[x].tag=(tmp2*res1%mod+tmp1*(1-res1+mod)%mod)%mod;
t[x].sum%=mod,t[x].tag%=mod,t[x].lc=t[b].lc,t[x].rc=t[b].rc;
}
} else {
ll las1=res1,las2=res2;
merge(t[x].rc,t[a].rc,t[b].rc,mid+1,r);
res1=(res1+t[t[a].rc].sum)%mod,res2=(res2+t[t[b].rc].sum)%mod,
merge(t[x].lc,t[a].lc,t[b].lc,l,mid);
t[x].sum=(t[t[x].lc].sum+t[t[x].rc].sum)%mod,res1=las1,res2=las2;
}
}
inline void total(int x,int l,int r) {
if(l==r) (ans+=1ll*l*H[l]%mod*t[x].sum%mod*t[x].sum%mod)%=mod;
else pushdown(x),total(t[x].lc,l,mid),total(t[x].rc,mid+1,r);
}
}using namespace Segment_Tree;
void dfs(int u) {
if(!son[u].size()) update(rt[u],1,cnt,v[u],1ll);
else if(son[u].size()==1) dfs(son[u][0]),rt[u]=rt[son[u][0]];
else {
int lc=son[u][0],rc=son[u][1];
dfs(lc),dfs(rc);
res1=res2=0,tmp1=p[u],tmp2=(1-p[u]+mod)%mod;
merge(rt[u],rt[lc],rt[rc],1,cnt);
}
}
int main() {
IN(n);
ll tmp=modpow(10000,mod-2);
for(int i=1;i<=n;++i) IN(fa[i]),son[fa[i]].push_back(i);
for(int i=1;i<=n;++i) {
if(!son[i].size()) IN(v[i]),H[++cnt]=v[i];
else IN(p[i]),(p[i]*=tmp)%=mod;
}
int last=cnt;
sort(H+1,H+1+cnt),cnt=1;
for(int i=2;i<=last;++i) if(H[i]!=H[cnt]) H[++cnt]=H[i];
for(int i=1;i<=n;++i) if(v[i]) v[i]=lower_bound(H+1,H+1+cnt,v[i])-H;
dfs(1),ans=0,total(rt[1],1,cnt);
printf("%lld\n",ans);
return 0;
}
0 条评论