花(Flower) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> dfn(n + 1, 0), sz(n + 1, 1), par(n + 1, 0), order;
    order.reserve(n);
    vector<int> stk = {1};
    while (!stk.empty()) {
        int u = stk.back();
        stk.pop_back();
        dfn[u] = (int)order.size() + 1;
        order.push_back(u);
        for (int i = (int)adj[u].size() - 1; i >= 0; --i) {
            int v = adj[u][i];
            if (v == par[u]) continue;
            par[v] = u;
            stk.push_back(v);
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        int u = order[i];
        if (par[u]) sz[par[u]] += sz[u];
    }
    int B = 1;
    while (B < n) B <<= 1;
    vector<long long> tree(2 * B, 0);
    for (int u = 1; u <= n; ++u) tree[B + dfn[u] - 1] = a[u];
    for (int i = B - 1; i >= 1; --i) tree[i] = max(tree[i << 1], tree[i << 1 | 1]);

    auto update = [&](int pos, long long val) {
        int p = B + pos - 1;
        tree[p] = val;
        for (p >>= 1; p >= 1; p >>= 1) tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
    };
    auto query = [&](int l, int r) {
        long long res = 0;
        for (l += B - 1, r += B - 1; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) res = max(res, tree[l++]);
            if (!(r & 1)) res = max(res, tree[r--]);
        }
        return res;
    };

    for (int i = 0; i < m; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int u;
            long long w;
            cin >> u >> w;
            update(dfn[u], w);
        } else {
            int u;
            cin >> u;
            cout << query(dfn[u], dfn[u] + sz[u] - 1) << "\n";
        }
    }
    return 0;
}