Solution

发现叶子节点的值都不样，所以可以线段树合并。

然后因为我们要维护一个后缀，所以我们先合并右儿子，在合并左儿子

Code 

//2019.1.14 8:59~10:15 PaperCloud#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 300005#define mod 998244353int const INV_1e4=796898467;int N,c[MN][3],fa[MN],p[MN];struct Node{    int val,id;    bool operator<(const Node&o)const {return val
     
      >1)inline void Modify(int &x,int l,int r,int val){    if(!x) x=++pin;t[x].lazy=t[x].p=1ll;if(l==r) return;    val<=mid?Modify(t[x].ls,l,mid,val):Modify(t[x].rs,mid+1,r,val);}ll L,R,P;inline void pushdown(int x){    if(t[x].lazy==1) return;    t[x].p=1ll*t[x].p*t[x].lazy%mod;    t[t[x].ls].lazy=1ll*t[t[x].ls].lazy*t[x].lazy%mod;    t[t[x].rs].lazy=1ll*t[t[x].rs].lazy*t[x].lazy%mod;    t[x].lazy=1;}inline void pushup(int x){t[x].p=(t[t[x].ls].p+t[t[x].rs].p)%mod;}inline int Merge(int x,int y){//  printf("%d %d\n",x,y);    if(!x&&!y)return 0;    pushdown(x),pushdown(y);    if(!y)    {        (L+=t[x].p)%=mod,t[x].lazy=1ll*t[x].lazy*(R+P-2ll*R*P%mod+mod)%mod;        pushdown(x);return x;    }    if(!x)    {        (R+=t[y].p)%=mod,t[y].lazy=1ll*t[y].lazy*(L+P-2ll*L*P%mod+mod)%mod;        pushdown(y);return y;    }    t[x].rs=Merge(t[x].rs,t[y].rs);t[x].ls=Merge(t[x].ls,t[y].ls);pushup(x);    return x;}inline void dfs(int x=1){    if(!c[x][0]) return;    else if(c[x][0]==1) dfs(c[x][1]),root[x]=root[c[x][1]];    else    {        dfs(c[x][1]),dfs(c[x][2]);L=R=0;P=p[x];        root[x]=Merge(root[c[x][1]],root[c[x][2]]);    }}inline void calc(int x=root[1],int l=1,int r=tot){    static ll ans=0;pushdown(x);    if(l==r)    {        (ans+=(1ll*l*a[l].val%mod*t[x].p%mod*t[x].p%mod)%mod)%=mod;        if(l==tot) printf("%lld\n",ans);        return;    }    calc(t[x].ls,l,mid);calc(t[x].rs,mid+1,r);}int main(){//  freopen("1.in","r",stdin);    N=read();register int i;    for(i=1;i<=N;++i) fa[i]=read(),c[fa[i]][++c[fa[i]][0]]=i;    for(i=1;i<=N;++i) if(c[i][0]>0) p[i]=1ll*read()*INV_1e4%mod; else a[++tot]=(Node){read(),i};    std::sort(a+1,a+tot+1);    for(i=1;i<=tot;++i) p[a[i].id]=i,Modify(root[a[i].id],1,tot,i);    dfs();calc();return 0;}
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！