Cod sursa(job #2642309)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 14 august 2020 17:03:12
Problema Heavy Path Decomposition Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.98 kb
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

int n, m;
const int N = 1e5;

vector <int> gr[1 + N];
int sz[1 + N], chain[1 + N], level[1 + N], value[1 + N];
int p[1 + N];
void dfsPrec (int node, int par) {
    p[node] = par;
    for (int son : gr[node])
        if (son != par) {
            dfsPrec (son, node);
            sz[node] += sz[son];
            level[son] = level[node] + 1;
        }
}
int ind[1 + N];
int seg[1 + 4 * N];
int nr;
void dfsChains (int node, int par) {
    int bigSon = 0;
    ind[node] = ++nr;
    for (int son : gr[node])
        if (son != par && sz[son] > sz[bigSon])
            bigSon = son;
    if (bigSon) {
        chain[bigSon] = chain[node];
        dfsChains (bigSon, node);
    }
    for (int son : gr[node])
        if (son != par && son != bigSon)
            dfsChains (son, node);
}

void updatePos (int node, int lb, int rb, int pos, int val) {
    if (lb == rb) {
        seg[node] = val;
        return;
    }
    int mid = (lb + rb) / 2;
    if (pos <= mid)
        updatePos (node * 2, lb, mid, pos, val);
    else
        updatePos (node * 2 + 1, mid + 1, rb, pos, val);
    seg[node] = max (seg[node * 2], seg[node * 2 + 1]);
}
int queryRange (int node, int lb, int rb, int lQ, int rQ) {
    if (lQ <= lb && rb <= rQ)
        return seg[node];
    int mid = (lb + rb) / 2;
    int ans = 0;
    if (mid >= lQ)
        ans = max (ans, queryRange (node * 2, lb, mid, lQ, rQ));
    if (mid + 1 <= rQ)
        ans = max (ans, queryRange (node * 2 + 1, mid + 1, rb, lQ, rQ));
    return ans;
}
int main () {
    freopen ("heavypath.in", "r", stdin);
    freopen ("heavypath.out", "w", stdout);

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> value[i];
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].pb (y);
        gr[y].pb (x);
    }
    for (int i = 1; i <= n; i++)
        chain[i] = i, sz[i] = 1;
    dfsPrec (1, 0);
    dfsChains (1, 0);
    for (int i = 1; i <= n; i++)
        updatePos (1, 1, n, ind[i], value[i]);
    while (m--) {
        int type;
        cin >> type;
        if (type == 0) {
            int x, newValue;
            cin >> x >> newValue;
            updatePos (1, 1, n, ind[x], newValue);
        }
        else {
            int x, y;
            cin >> x >> y;
            int ans = 0;
            while (chain[x] != chain[y]) {
                if (level[chain[x]] < level[chain[y]])
                    swap (x, y);
                ans = max (ans, queryRange (1, 1, n, ind[chain[x]], ind[x]));
                x = p[chain[x]];
            }
            if (level[x] > level[y])
                swap (x, y);
            ans = max (ans, queryRange (1, 1, n, ind[x], ind[y]));
            cout << ans << "\n";
        }
    }
    return 0;
}