CSES 2134：Path Queries II

CSES 2134：Path Queries II

題目大意：給你一棵樹，請你求節點 $a$ 到節點 $b$ 路徑上的最大值，並且可以中途改變節點值。

解法：重鏈剖分 $+$ 線段樹。第一次寫重鏈剖分，好難喔。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 200005;

int fa[SIZE], dfcnt;
int wei[SIZE], dep[SIZE], dfn[SIZE], son[SIZE], tp[SIZE];
int arr[SIZE];
vector<int> edge[SIZE];

void dfs1 (int pos, int f, int h) {
    wei[pos] = 1, fa[pos] = f, dep[pos] = h;
    for (int np : edge[pos]) {
        if (np != f) {
            dfs1 (np, pos, h + 1);
            if (wei[np] > wei[son[pos]])
                son[pos] = np;
            wei[pos] += wei[np];
        }
    }
}

void dfs2 (int pos, int t) {
    if (!pos)
        return;
    dfn[pos] = ++dfcnt, tp[pos] = t;
    dfs2 (son[pos], t);
    for (int np : edge[pos]) {
        if (np != fa[pos] && np != son[pos]) {
            dfs2 (np, np);
        }
    }
}

int seg[4 * SIZE];

void build (int pos, int l, int r) {
    if (l == r)
        seg[pos] = arr[l];
    else {
        int mid = (l + r) / 2;
        build (lpos, l, mid);
        build (rpos, mid + 1, r);
        seg[pos] = max (seg[lpos], seg[rpos]);
    }
}

void modify (int pos, int l, int r, int p, int x) {
    if (l == r)
        seg[pos] = arr[l] = x;
    else {
        int mid = (l + r) / 2;
        if (p <= mid)
            modify (lpos, l, mid, p, x);
        else
            modify (rpos, mid + 1, r, p, x);
        seg[pos] = max (seg[lpos], seg[rpos]);
    }
}

int query (int pos, int l, int r, int L, int R) {
    if (l == L && r == R)
        return seg[pos];
    int mid = (L + R) / 2;
    if (r <= mid)
        return query (lpos, l, r, L, mid);
    if (l > mid)
        return query (rpos, l, r, mid + 1, R);
    return max (query (lpos, l, mid, L, mid), query (rpos, mid + 1, r, mid + 1, R));
}

void solve() {
    int n, q;
    cin >> n >> q;

    int temp[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> temp[i];
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        edge[a].push_back (b);
        edge[b].push_back (a);
    }

    dfs1 (1, 1, 1);
    dfs2 (1, 1);

    for (int i = 1; i <= n; i++)
        arr[dfn[i]] = temp[i];
    build (1, 1, n);

    while (q--) {
        int ty;
        cin >> ty;
        if (ty == 1) {
            int p, x;
            cin >> p >> x;
            modify (1, 1, n, dfn[p], x);
        } else {
            int a, b, ans = 0;
            cin >> a >> b;
            while (1) {
                if (dep[tp[a]] > dep[tp[b]])
                    swap (a, b);
                if (tp[a] == tp[b]) {
                    if (dfn[a] > dfn[b])
                        swap (a, b);
                    ans = max (ans, query (1, dfn[a], dfn[b], 1, n));
                    break;
                }
                ans = max (ans, query (1, dfn[tp[b]], dfn[b], 1, n));
                b = fa[tp[b]];
            }
            cout << ans << ' ';
        }
    }
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！