Untitled

 avatar
unknown
plain_text
a year ago
3.5 kB
4
Indexable
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
void File() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("errors.txt", "w", stderr);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
struct SegTree {
    const long long ID{};
    static long long cmb(long long a, long long b) { return max(a, b); }
    void pull(int p) { seg[p] = cmb(seg[2 * p], seg[2 * p + 1]); }
    int n{};
    vector<long long> seg;
    void init(int _n) {
        for (n = 1; n <= _n;) n *= 2;
        seg.assign(2 * n, ID);
    }
    void upd(int p, long long val) {
        seg[p += n] = val;
        for (p /= 2; p; p /= 2) pull(p);
    }
    long long query(int l, int r) {
        long long ra = ID, rb = ID;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
            if (l & 1) ra = cmb(ra, seg[l++]);
            if (r & 1) rb = cmb(seg[--r], rb);
        }
        return cmb(ra, rb);
    }
};
struct HLD {
    vector<int> par, head, heavy, pos, depth;
    int timer{};
    SegTree seg;
    explicit HLD(const vector<vector<int>> &adj, vector<int> &v) {
        int n = (int) adj.size();
        par.assign(n, 0), head.assign(n, 0);
        heavy.assign(n, -1), pos.assign(n, 0);
        depth.assign(n, 0), timer = 0;
        dfs(0, adj);
        decomposition(0, 0, adj);
        seg.init(n);
        for (int i = 0; i < n; ++i)
            seg.upd(pos[i], v[i]);
    }
    int dfs(int u, const vector<vector<int>> &adj) {
        int sz = 1, MX = 0;
        for (auto &v: adj[u]) {
            if (v == par[u]) continue;
            par[v] = u, depth[v] = depth[u] + 1;
            int s = dfs(v, adj);
            if (s > MX)
                MX = s, heavy[u] = v;
        }
        return sz;
    }
    void decomposition(int u, int h, const vector<vector<int>> &adj) {
        pos[u] = timer++, head[u] = h;
        if (~heavy[u])
            decomposition(heavy[u], h, adj);
        for (auto &v: adj[u])
            if (v != par[u] && v != heavy[u])
                decomposition(v, v, adj);
    }
    static long long calc(long long x, long long y) {
        return max(x, y);
    }
    long long getDS(int u, int v) {
        return seg.query(pos[u], pos[v]);
    }
    long long query(int u, int v) {
        long long res = 0;
        for (; head[u] != head[v]; v = par[head[v]]) {
            if (depth[head[u]] > depth[head[v]])
                swap(u, v);
            res = calc(res, getDS(head[v], v));
        }
        if (depth[u] > depth[v])
            swap(u, v);
        res = calc(res, getDS(u, v));
        return res;
    }
};
int main() {
    File();
    int n, q;
    cin >> n >> q;
    vector<int> val(n);
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; ++i)
        cin >> val[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    HLD hld(adj, val);
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if(t == 1) {
            ll u, v;
            cin >> u >> v;
            hld.seg.upd(hld.pos[u - 1], v);
        } else {
            int u, v;
            cin >> u >> v;
            cout << hld.query(u - 1, v - 1) << " ";
        }
    }
    return 0;
}
Editor is loading...
Leave a Comment