[PKUWC2018] Minimax

[PKUWC2018]Minimax

发现叶子权值全不一样,直觉告诉我们是线段树合并。

发现是二叉树,直觉告诉我们分类讨论。

于是,可以写出DP方程。

f_{x,k}表示x点,取值为k的概率。

如果从左儿子转移来:

f_{x,k}=f_{ls,k}(p_x \sum_{i=1}^{k-1}f_{rs,i}+(1-p_x)\sum_{i=k+1}^mf_{rs,i})

如果从右儿子转移来:

f_{x,k}=f_{rs,k}(p_x \sum_{i=1}^{k-1}f_{ls,i}+(1-p_x)\sum_{i=k+1}^mf_{ls,i})

这个柿子可以线段树合并优化。

递归合并的时候,维护两个前缀和,两个后缀和,就是柿子里那些东西。

线段树合并保证复杂度,重要的一点是如果一边空了就返回。

具体到这道题,如果一棵树某子树空了,那么另一棵树转移乘的东西就不变了。线段树打个lazytag。

然后代码完全不会写了...各种坑...参考了各种博客,调了很久之后:

#include <bits/stdc++.h>

inline int rd() {
    int a = 1, b = 0; char c = getchar();
    while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
    while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
    return a ? b : -b;
}

typedef long long LL;
const int N = 3e5 + 233, P = 998244353, INV = 796898467;

int n, ans, son[N][2], raw_val[N], val[N], tmp[N], nn,
    ls[N * 50], rs[N * 50], tag[N * 50], f[N * 50], root[N], num;

inline void pushup(int p) {
    f[p] = (f[ls[p]] + f[rs[p]]) % P;
}

inline void pushdown(int p) {
    if (tag[p] != 1) {
        tag[ls[p]] = (LL)tag[ls[p]] * tag[p] % P;
        tag[rs[p]] = (LL)tag[rs[p]] * tag[p] % P;
        f[ls[p]] = (LL)f[ls[p]] * tag[p] % P;
        f[rs[p]] = (LL)f[rs[p]] * tag[p] % P;
        tag[p] = 1;
    }
}

void single_init(int &p, int x, int L, int R) {
    if (!p) p = ++num, tag[p] = 1;
    if (L == R) { f[p] = 1; return; }
    int mid = (L + R) >> 1;
    if (x <= mid) single_init(ls[p], x, L, mid);
    else single_init(rs[p], x, mid + 1, R);
    pushup(p);
}

int merge(int x, int y, int la, int ra, int lb, int rb, int p) {
    if (!x && !y) return 0;
    if (x) pushdown(x);
    if (y) pushdown(y);
    if (x && !y) {
        int tmp = ((LL)p * lb % P + (LL)(1 - p + P) % P * rb % P) % P;
        f[x] = (LL)f[x] * tmp % P;
        tag[x] = (LL)tag[x] * tmp % P;
        return x;
    }
    if (!x && y) {
        int tmp = ((LL)p * la % P + (LL)(1 - p + P) % P * ra % P) % P;
        f[y] = (LL)f[y] * tmp % P;
        tag[y] = (LL)tag[y] * tmp % P;
        return y;
    }
    int now = ++num;
    tag[now] = 1;
    int a = f[ls[x]], b = f[ls[y]];
    ls[now] = merge(ls[x], ls[y], la, (ra + f[rs[x]]) % P, lb, (rb + f[rs[y]]) % P, p);
    rs[now] = merge(rs[x], rs[y], (la + a) % P, ra, (lb + b) % P, rb, p);
    pushup(now);
    return now;
}

void dfs_solve(int x) {
    if (!son[x][0] && !son[x][1]) {
        single_init(root[x], val[x], 1, n);
        return;
    }
    if (son[x][0] && !son[x][1]) {
        dfs_solve(son[x][0]);
        root[x] = root[son[x][0]];
        return;
    }
    if (son[x][0] && son[x][1]) {
        dfs_solve(son[x][0]);
        dfs_solve(son[x][1]);
        int p = (LL)val[x] * INV % P;
        root[x] = merge(root[son[x][0]], root[son[x][1]], 0, 0, 0, 0, p);
    }
}

void calc_ans(int x, int L, int R) {
    if (!x) return;
    pushdown(x);
    if (L == R) {
        ans = (ans + (LL)L * tmp[L] % P * f[x] % P * f[x] % P) % P;
        return;
    }
    int mid = (L + R) >> 1;
    calc_ans(ls[x], L, mid);
    calc_ans(rs[x], mid + 1, R);
}

signed main() {
    n = rd(); rd();
    for (int i = 2; i <= n; ++i) {
        int x = rd();
        if (son[x][0]) son[x][1] = i;
        else son[x][0] = i;
    }
    for (int i = 1; i <= n; ++i)
        val[i] = rd();
    for (int i = 1; i <= n; ++i)
        if (!son[i][0] && !son[i][1])
            tmp[++nn] = val[i];
    std::sort(tmp + 1, tmp + nn + 1);
    for (int i = 1; i <= n; ++i)
        if (!son[i][0] && !son[i][1])
            val[i] = std::lower_bound(tmp + 1, tmp + nn + 1, val[i]) - tmp;
    dfs_solve(1);
    calc_ans(root[1], 1, n);
    std::cout << ans << std::endl;
    return 0;
}

发表评论

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