LibreOJ 2537 「PKUWC2018」Minimax

首先离散化。
考虑一个简单 O(n2) 树形 DP：设 fu,i 表示 u 取到 i 的概率，l,r 分别为 u 的左 / 右儿子。
那么有 fu,i=fl,i[pui−1∑j=1fr,j+(1−pu)m∑j=i+1fr,j]+fr,i[pui−1∑j=1fl,j+(1−pu)m∑j=i+1fl,j]

前后缀和优化即可。

事实上，这种形式的转移可以使用线段树合并来优化（即所谓「整体 DP」）。
由于没有相同值，合并到最后一定只剩一边非空。
在线段树合并的过程中不难算出两棵线段树上目前的前后缀和，直接打上乘法标记即可。

另外，10−4≡796898467(mod998244353)。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3e5;
const int mod = 998244353;
const int inv1e4 = 796898467;
int n;
int fa[N + 5],ch[N + 5][2];
int a[N + 5],ind[N + 5],len;
int d[N + 5],ans;
namespace SEG
{
    struct node
    {
        int sum,tag;
        int ls,rs;
    } seg[(N << 5) + 5];
    inline void push(int p)
    {
        if(seg[p].tag ^ 1)
        {
            if(seg[p].ls)
                seg[seg[p].ls].sum = (long long)seg[seg[p].ls].sum * seg[p].tag % mod,
                seg[seg[p].ls].tag = (long long)seg[seg[p].ls].tag * seg[p].tag % mod;
            if(seg[p].rs)
                seg[seg[p].rs].sum = (long long)seg[seg[p].rs].sum * seg[p].tag % mod,
                seg[seg[p].rs].tag = (long long)seg[seg[p].rs].tag * seg[p].tag % mod;
            seg[p].tag = 1;
        }
    }
    void insert(int x,int &p,int tl,int tr)
    {
        static int tot = 0;
        !p && (seg[p = ++tot].tag = 1);
        if(tl == tr)
        {
            seg[p].sum = 1;
            return ;
        }
        push(p);
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
        seg[p].sum = (seg[seg[p].ls].sum + seg[seg[p].rs].sum) % mod;
    }
    int merge(int p,int q,int ptag,int qtag,int v)
    {
        if(!p && !q)
            return 0;
        if(!p)
        {
            seg[q].sum = (long long)seg[q].sum * qtag % mod,
            seg[q].tag = (long long)seg[q].tag * qtag % mod;
            return q;
        }
        if(!q)
        {
            seg[p].sum = (long long)seg[p].sum * ptag % mod,
            seg[p].tag = (long long)seg[p].tag * ptag % mod;
            return p;
        }
        push(p),push(q);
        int plsum = seg[seg[p].ls].sum,prsum = seg[seg[p].rs].sum;
        int qlsum = seg[seg[q].ls].sum,qrsum = seg[seg[q].rs].sum;
        seg[p].ls = merge(seg[p].ls,seg[q].ls,(ptag + (long long)(1 - v + mod) * qrsum) % mod,(qtag + (long long)(1 - v + mod) * prsum) % mod,v),
        seg[p].rs = merge(seg[p].rs,seg[q].rs,(ptag + (long long)v * qlsum) % mod,(qtag + (long long)v * plsum) % mod,v),
        seg[p].sum = (seg[seg[p].ls].sum + seg[seg[p].rs].sum) % mod;
        return p;
    }
    void dfs(int p,int tl,int tr)
    {
        if(tl == tr)
        {
            d[tl] = seg[p].sum;
            return ;
        }
        push(p);
        int mid = tl + tr >> 1;
        seg[p].ls && (dfs(seg[p].ls,tl,mid),1);
        seg[p].rs && (dfs(seg[p].rs,mid + 1,tr),1);
    }
}
int rt[N + 5];
void dfs(int p)
{
    if(ch[p][1])
        dfs(ch[p][0]),dfs(ch[p][1]),
        rt[p] = SEG::merge(rt[ch[p][0]],rt[ch[p][1]],0,0,a[p]);
    else if(ch[p][0])
        dfs(ch[p][0]),
        rt[p] = rt[ch[p][0]];
    else
        SEG::insert(a[p],rt[p],1,len);
}
int main()
{
    scanf("%d%*d",&n);
    for(register int i = 2;i <= n;++i)
        scanf("%d",fa + i),ch[fa[i]][(bool)ch[fa[i]][0]] = i;
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),ch[i][0] ? (a[i] = (long long)a[i] * inv1e4 % mod) : (ind[++len] = a[i]);
    sort(ind + 1,ind + len + 1),len = unique(ind + 1,ind + len + 1) - ind - 1;
    for(register int i = 1;i <= n;++i)
        !ch[i][0] && (a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind);
    dfs(1),SEG::dfs(rt[1],1,len);
    for(register int i = 1;i <= len;++i)
        ans = (ans + (long long)i * ind[i] % mod * d[i] % mod * d[i]) % mod;
    printf("%d\n",ans);
}