题解：P11163 [BalkanOI 2023] Weights

· · 题解

可爱猫猫题

令 f_u 表示点 u 的答案，即让以点 u 为根的子树“超平衡”时，这个子树最少多重。那么有一个递推式是 f_u=2\times\max\{f_l,f_r\}，即先让其左右子树分别“超平衡”，再平衡自己。由此，有一个比较显然的结论是 f_u = 2^{-d_u}\times\max 2^{d_x}a_x，其中 x 为 u 子树内的一个叶子，d_u 表示 u 在树上的深度，d_x 同理。证明可以考虑从下往上归纳，对于叶子显然成立，非叶子可以假设左右儿子成立，然后由上述递推式推得。

现在我们要求的问题即是单点修改、求子树 \max。但是由于这个东西比较大，不方便直接比较大小，所以实现时直接将答案存储为 2^p\times q 的形式。对于比较形如 2^{p_1}\times q_1 与 2^{p_2}\times q_2 的数的大小的问题，可以发现当 |p_1-p_2|\ge30 时可以直接判断，否则可以暴力计算比较。

然后就做完了，时间复杂度 O(n\log n)。

贴个核心代码，省略了一些缺省源，应该不影响阅读。

const int mod = 998244353;
using mint = Source::mint<mod>;

int n, q, a[400010], dfn[400010], siz[400010], dep[400010], cnt;
mint pw[400010];
vector<int> e[400010];

struct pint {
    int p, q;

    pint(int a = 0, int b = 0) {
        p = a;
        q = b;
    }

    bool operator < (pint b) const {
        int dp = p - b.p;
        if (dp > 29) return false;
        if (dp < -29) return true;
        if (dp < 0) {
            dp = -dp;
            return pw[dp].x * 1LL * b.q > q;
        }
        return pw[dp].x * 1LL * q < b.q;
    }
};

class segmentTree {
    private :
        pint tree[1600010];

        inline int getLeft(int u) { return u << 1; }

        inline int getRight(int u) { return u << 1 | 1; }

        inline void pushUp(int u) { tree[u] = max(tree[getLeft(u)], tree[getRight(u)]); }

    public :
        void update(int u, int l, int r, int x, pint k) {
            if (l == r) {
                tree[u] = k;
                return;
            }
            if (x <= (l + r) / 2) update(getLeft(u), l, (l + r) / 2, x, k);
            else update(getRight(u), (l + r) / 2 + 1, r, x, k);
            pushUp(u);
        }

        pint query(int u, int l, int r, int x, int y) {
            if (x <= l && r <= y) return tree[u];
            if (y <= (l + r) / 2) return query(getLeft(u), l, (l + r) / 2, x, y);
            if (x > (l + r) / 2) return query(getRight(u), (l + r) / 2 + 1, r, x, y);
            return max(query(getLeft(u), l, (l + r) / 2, x, y), query(getRight(u), (l + r) / 2 + 1, r, x, y));
        }
}tree;

void DFS(int u, int p) {
    siz[u] = 1;
    dfn[u] = ++ cnt;
    dep[u] = dep[p] + 1;
    for (int v : e[u]) if (v != p) DFS(v, u), siz[u] += siz[v];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    pw[0] = 1;
    rep (i,1,n + n + 1) pw[i] = pw[i - 1] * 2;
    rep (i,1,n) {
        char op1, op2;
        int u1, u2;
        cin >> op1 >> u1 >> op2 >> u2;
        if (op1 == 'W') u1 += n;
        if (op2 == 'W') u2 += n;
        e[i].emplace_back(u1);
        e[i].emplace_back(u2);
    }
    rep (i,n + 1,n + n + 1) cin >> a[i];
    DFS(1, 0);
    rep (i,1,n + 1) tree.update(1, 1, n + n + 1, dfn[i + n], pint(dep[i + n], a[i + n]));
    rep (i,1,q) {
        int op;
        cin >> op;
        if (op == 1) {
            int u, k;
            cin >> u >> k;
            u += n;
            a[u] = k;
            tree.update(1, 1, n + n + 1, dfn[u], pint(dep[u], a[u]));
        } else {
            int u;
            cin >> u;
            pint res = tree.query(1, 1, n + n + 1, dfn[u], dfn[u] + siz[u] - 1);
            mint ans = pw[res.p] * res.q;
            ans *= Source::quickPow<mod>(Source::quickPow<mod>(2, dep[u]), mod - 2);
            cout << ans.x << '\n';
        }
    }
    return 0;
}