6G33Du - Online C++0x Compiler & Debugging Tool

// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "gen"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 200000 + 5;
const int S = 350;
int n, m, q, a[N];
vector<int> G[N];
int pos[N], timer = 0, h[N], minHigh[N << 1][20], tour[N << 1];

void dfs(int u, int par) {
    pos[u] = ++timer;
    tour[timer] = u;
    for(int v : G[u]) if (v != par) {
        h[v] = h[u] + 1;
        dfs(v, u);
        tour[++timer] = u;
    }
}

#define MIN_HIGH(x, y) (h[x] < h[y] ? x : y)
int LCA(int u, int v) {
    int l = pos[u], r = pos[v];
    if (l > r) swap(l, r);
    int k = __lg(r - l + 1);
    return MIN_HIGH(minHigh[l][k], minHigh[r - MASK(k) + 1][k]);
}

int dist(int u, int v) {
    int p = LCA(u, v);
    return h[u] + h[v] - 2 * h[p];
}

ll lazy_add[N / S + 5]; // tất cả các thằng trong block đều cộng thêm lazy_add[B]
int lazy_set[N / S + 5]; // giá trị hiện tại đang dc gán
int first_set[N / S + 5]; // giá trị đầu tiên dc gán
ll ans[N]; // kết quả của nhân viên i
ll val[N / S + 5][N]; // giá trị hiện tại của giá trị u trong block B
ll old[N]; // để ko phải reset mảng val, dùng mảng old để trừ đi những giá trị có sẵn trước khi add

void rebuild(int B) {
    if (lazy_set[B] == 0) return;
    FOR(i, B * S, (B + 1) * S - 1) {
        ans[i] += val[B][a[i]] - old[i] - dist(a[i], first_set[B]);
        a[i] = lazy_set[B];
        old[i] = val[B][a[i]];
    }
    first_set[B] = -1;
    lazy_set[B] = 0;
}

void init(void) {
    cin >> n >> m >> q;
    REP(i, m) cin >> a[i];
    FOR(i, 2, n) {
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
}

void process(void) {
    dfs(1, -1);
    FOR(i, 1, timer) minHigh[i][0] = tour[i];
    FOR(j, 1, 19) FOR(i, 1, timer - MASK(j) + 1)
        minHigh[i][j] = MIN_HIGH(minHigh[i][j - 1], minHigh[i + MASK(j - 1)][j - 1]);

    memset(first_set, -1, sizeof first_set);
    while(q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            FOR(B, 0, m / S)
                if (lazy_set[B] == u)
                    lazy_add[B] += v;
                else if (lazy_set[B] == 0)
                    val[B][u] += v;
        } else if (type == 2) {
            int l, r, z;
            cin >> l >> r >> z;
            l--; r--;
            if (l / S == r / S) {
                rebuild(l / S);
                FOR(i, l, r) {
                    ans[i] += val[l / S][a[i]] - old[i] - dist(a[i], z);
                    a[i] = z;
                    old[i] = val[l / S][z];
                }
                continue;
            }
            rebuild(l / S);
            rebuild(r / S);
            FOR(i, l, (l / S + 1) * S - 1) {
                ans[i] += val[l / S][a[i]] - old[i] - dist(a[i], z);
                a[i] = z;
                old[i] = val[l / S][z];
            }
            FOR(i, (r / S) * S, r) {
                ans[i] += val[r / S][a[i]] - old[i] - dist(a[i], z);
                a[i] = z;
                old[i] = val[r / S][z];
            }
            FOR(i, l / S + 1, r / S - 1) {
                if (first_set[i] == -1)
                    first_set[i] = z;
                if (lazy_set[i] > 0) lazy_add[i] -= dist(lazy_set[i], z);
                lazy_set[i] = z;
            }
        } else {
            int u; cin >> u;
            u--;
            rebuild(u / S);
            cout << ans[u] + lazy_add[u / S] + val[u / S][a[u]] - old[u] << '\n';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}