Untitled

mail@pastecode.io avatar
unknown
plain_text
21 days ago
4.7 kB
1
Indexable
Never
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<long long, long long>
using namespace std;
 
const int MAX = 3e5 + 5;
vector<int> edges[MAX];
ll tree[MAX * 4];
ll lazy[MAX * 4];
int level[MAX];
int parent[MAX];
int reorder[MAX];
int heavy[MAX];
int subg_size[MAX];
int chain_top[MAX];
int dp[MAX][20];
int cnt = 0;
 
void push(ll idx, int left, int right) {
    if (lazy[idx] != 0) {
        tree[idx] += lazy[idx];
        if (left != right) {
            lazy[idx * 2] += lazy[idx];
            lazy[idx * 2 + 1] += lazy[idx];
        }
        lazy[idx] = 0;
    }
 
    return;
}
 
void update(int idx, int left, int right, int a, int b, ll val) {
    push(idx, left, right);
    if (left > b || right < a) return;
 
    if (left >= a && right <= b) {
        tree[idx] += (right - left + 1) * val;
        if (left != right) {
            lazy[idx * 2] += val;
            lazy[idx * 2 + 1] += val;
        }
        return;
    }
 
    int mid = (left + right) / 2;
    update(idx * 2, left, mid, a, b, val);
    update(idx * 2 + 1, mid + 1, right, a, b, val);
    tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
    return;
}
 
ll query(int idx, int left, int right, int a, int b) {
    push(idx, left, right);
    if (left > b || right < a) return 0;
    if (left >= a && right <= b) return tree[idx];
 
    int mid = (left + right) / 2;
    return query(idx * 2, left, mid, a, b) + query(idx * 2 + 1, mid + 1, right, a, b);
}
 
 
void dfs(int a, int prev) {
    level[a] = level[prev] + 1;
    dp[a][0] = prev;
    for (int j = 1; j < 20; j++) dp[a][j] = dp[dp[a][j - 1]][j - 1];
 
    for (auto e : edges[a]) {
        if (e == prev) continue;
        dfs(e, a);
    }
 
    return;
}
 
int lca(int a, int b) {
    if (level[a] < level[b]) swap(a, b);
    int diff = level[a] - level[b];
    for (int j = 0; j < 20; j++) {
        if (diff & 1 << j) a = dp[a][j];
    }
 
    if (a == b) return a;
    for (int j = 19; j >= 0; j--) {
        if (dp[a][j] == dp[b][j]) continue;
        a = dp[a][j];
        b = dp[b][j];
    }
 
    return dp[a][0];
}
 
void dfs2(int a, int prev) {
    subg_size[a] = 1;
    parent[a] = prev;
    for (auto e : edges[a]) {
        if (e == prev) continue;
        dfs2(e, a);
        subg_size[a] += subg_size[e];
        if (subg_size[heavy[a]] < subg_size[e]) heavy[a] = e;
    }
 
    return;
}
 
void dfs3(int a, int prev) {
    reorder[a] = ++cnt;
    if (!heavy[a]) return;
    dfs3(heavy[a], a);
    for (auto e : edges[a]) {
        if (e == prev || e == heavy[a]) continue;
        dfs3(e, a);
    }
 
    return;
}
 
void dfs4(int a, int prev) {
    for (auto e : edges[a]) {
        if (e == prev) continue;
        if (e == heavy[a]) chain_top[e] = chain_top[a];
        else chain_top[e] = e;
        dfs4(e, a);
    }
 
    return;
}
 
ll calc(int a, int b, int n) {
    ll ans = query(1, 0, n, reorder[a], reorder[a]);
    while(a != b) {
        int nxt;
        if (chain_top[a] == a) nxt = parent[a];
        else if (level[chain_top[a]] >= level[b]) nxt = chain_top[a];
        else nxt = b;
 
        ans += query(1, 0, n, reorder[nxt], reorder[parent[a]]);
        a = nxt;
 
    }
 
    return ans;
}
 
void update_path(int a, int b, int n, ll val) {
    update(1, 0, n, reorder[a], reorder[a], val);
    while(a != b) {
        int nxt;
        if (chain_top[a] == a) nxt = parent[a];
        else if (level[chain_top[a]] >= level[b]) nxt = chain_top[a];
        else nxt = b;
 
        update(1, 0, n, reorder[nxt], reorder[parent[a]], val);
        a = nxt;
    }
 
    return;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n, q, a, b, t;
    cin >> n >> q;
    vector<ll> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
 
    chain_top[1] = 1;
    dfs(1, 0);
    dfs2(1, 0);
    dfs3(1, 0);
    dfs4(1, 0);
 
    for (int i = 1; i <= n; i++) update(1, 0, n, reorder[i], reorder[i], v[i]);
 
    while(q--) {
        cin >> t >> a >> b;
        if (t == 1) {
            ll cur_val = query(1, 0, n, reorder[a], reorder[a]);
            update(1, 0, n, reorder[a], reorder[a], b - cur_val);
        }
        else {
            int c = lca(a, b);
            cout << calc(a, c, n) + calc(b, c, n) - query(1, 0, n, reorder[c], reorder[c]) << "\n";
        }
    }
 
    return 0;
}
Leave a Comment