题目传送门 pwp

首先我们可以想到一个显而易见的 $\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;
}
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code