Loj#2537.「PKUWC 2018」Minimax | wzf2000's blog

Loj#2537.「PKUWC 2018」Minimax

Loj#2537.「PKUWC 2018」Minimax 题解

题意:

  • 略。

题解:

  • 显然可以自底向上线段树合并。
  • 概率修改只需要打个标记就好了。
  • 有一点小细节。
  • 时间复杂度 $O(n\log n)$。

代码:

#include <bits/stdc++.h>
#define gc getchar()
#define lson ls[cur],l,mid
#define rson rs[cur],mid+1,r
using namespace std;
typedef long long ll;
const int mod=998244353;
const int M=10000009;
const int N=300009;
int n,m,fa[N],w[N],is_leaf[N],first[N],number,root[N],ls[M],rs[M],sum[M],cnt;
int s1,s2,Ans,tg[M];
vector<int> q;
struct edge
{
    int to,next;
    void add(int x,int y)
    {
        to=y,next=first[x],first[x]=number;
    }
}e[N];
int read()
{
    int x=1;
    char ch;
    while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
    int s=ch-'0';
    while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
    return s*x;
}
int ksm(int x,int y,int ret=1)
{
    for (;y;y>>=1,x=(ll)x*x%mod)
        if (y&1) ret=(ll)ret*x%mod;
    return ret;
}
void ins(int &cur,int l,int r,int x)
{
    if (!cur) tg[cur=++cnt]=1,sum[cur]=1;
    if (l==r) return;
    int mid=(l+r>>1);
    if (x<=mid) ins(lson,x);
    else ins(rson,x);
}
void down(int cur)
{
    if (tg[cur]==1) return;
    if (ls[cur])
        sum[ls[cur]]=(ll)sum[ls[cur]]*tg[cur]%mod,tg[ls[cur]]=(ll)tg[ls[cur]]*tg[cur]%mod;
    if (rs[cur])
        sum[rs[cur]]=(ll)sum[rs[cur]]*tg[cur]%mod,tg[rs[cur]]=(ll)tg[rs[cur]]*tg[cur]%mod;
    tg[cur]=1;
}
void merge(int &cur,int cur1,int cur2,int l,int r,int p)
{
    if (!cur1&&!cur2) return;
    if (!cur1)
    {
        cur=cur2;
        s2=(s2+sum[cur])%mod;
        sum[cur]=(ll)sum[cur]*((ll)s1*p%mod+(ll)(mod+1-s1)*(mod+1-p)%mod)%mod;
        tg[cur]=(ll)tg[cur]*((ll)s1*p%mod+(ll)(mod+1-s1)*(mod+1-p)%mod)%mod;
        return;
    }
    if (!cur2)
    {
        cur=cur1;
        s1=(s1+sum[cur])%mod;
        sum[cur]=(ll)sum[cur]*((ll)s2*p%mod+(ll)(mod+1-s2)*(mod+1-p)%mod)%mod;
        tg[cur]=(ll)tg[cur]*((ll)s2*p%mod+(ll)(mod+1-s2)*(mod+1-p)%mod)%mod;
        return;
    }
    down(cur1),down(cur2);
    int mid=(l+r>>1);
    tg[cur=++cnt]=1;
    merge(ls[cur],ls[cur1],ls[cur2],l,mid,p);
    merge(rs[cur],rs[cur1],rs[cur2],mid+1,r,p);
    sum[cur]=(sum[ls[cur]]+sum[rs[cur]])%mod;
}
void dfs(int x)
{
    if (!first[x])
    {
        ins(root[x],1,m,w[x]);
        return;
    }
    if (!e[first[x]].next)
    {
        dfs(e[first[x]].to);
        root[x]=root[e[first[x]].to];
        return;
    }
    int lc=e[first[x]].to,rc=e[e[first[x]].next].to;
    dfs(lc),dfs(rc);
    s1=0,s2=0;
    merge(root[x],root[lc],root[rc],1,m,w[x]);
}
void solve(int cur,int l,int r)
{
    if (l==r)
    {
        Ans=(Ans+(ll)l*q[l-1]%mod*sum[cur]%mod*sum[cur])%mod;
        return;
    }
    int mid=(l+r>>1);
    down(cur);
    solve(lson),solve(rson);
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++) is_leaf[i]=1;
    for (int i=1;i<=n;i++)
        fa[i]=read(),is_leaf[fa[i]]=0,e[++number].add(fa[i],i);
    for (int i=1;i<=n;i++)
    {
        w[i]=read();
        if (!is_leaf[i]) w[i]=(ll)w[i]*ksm(10000,mod-2)%mod;
        else q.push_back(w[i]);
    }
    sort(q.begin(),q.end());
    q.erase(unique(q.begin(),q.end()),q.end());
    for (int i=1;i<=n;i++)
        is_leaf[i]?w[i]=lower_bound(q.begin(),q.end(),w[i])-q.begin()+1:0;
    m=q.size();
    dfs(1);
    solve(root[1],1,m);
    printf("%d\n",Ans);
    return 0;
}