Cod sursă (job #466002)

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

#define N 200010
int n, a[N], p[N], m, sz[N], pnod[N], mxc[N], chain[N], nrl = 1;
int cnt[N], ord[N], k, fw[N], bgn[N], stotal = 0;
int sum_subarb[N], start_node[N];
vector <int> v[N];
multiset <int> S[N];

void updatefw(int pos, int val){
    for (; pos <= n; pos += (pos & -pos)) fw[pos] += val;
}

void update(int nod, int val){
    updatefw(bgn[chain[nod]] + ord[nod] - 1, val);

    int curr_node = start_node[chain[nod]];
    int father = p[chain[nod]];

    if (father){
        S[father].erase(S[father].find(sum_subarb[curr_node]));
        sum_subarb[curr_node] += val;
        S[father].insert(sum_subarb[curr_node]);
    }
    else sum_subarb[curr_node] += val;
    if (father) update(father, val);
}

int get(int pos){
    int rs = 0;
    for (; pos; pos -= (pos & -pos)) rs += fw[pos];
    return rs;
}

int query(int x, int y){
    return (get(y) - get(x - 1));
}

int getsz(int q, int pr){
    sz[q] = 1;
    int mx = 0, idx;
    for (auto it: v[q]){
        if (it == pr) continue;
        pnod[it] = q;
        int tt = getsz(it, q);
        if (tt > mx) mx = tt, idx = it;
        sz[q] += tt;
    }
    if (mx) mxc[q] = idx;
    return sz[q];
}

void hld(int q, int pr){
    ++k;
    chain[q] = nrl;
    ord[q] = ++cnt[nrl];
    if (ord[q] == 1) bgn[nrl] = k, start_node[nrl] = q;
    sum_subarb[start_node[chain[q]]] += a[q];
    updatefw(k, a[q]);
    if (mxc[q])
        hld(mxc[q], q), sum_subarb[start_node[chain[q]]] += sum_subarb[mxc[q]];
    for (auto it: v[q]){
        if (it == pr || it == mxc[q]) continue;
        p[++nrl] = q; hld(it, q);
        sum_subarb[start_node[chain[q]]] += sum_subarb[it];
        S[q].insert(sum_subarb[it]);
        updatefw(bgn[chain[q]] + ord[q]-1, sum_subarb[it]);
    }
}

int ask(int id){
    int aux = 0, aux2 = 0, mx = 0;
    if (S[id].size()) aux = *S[id].rbegin();
    int st = bgn[chain[id]] + ord[id];
    int dr = bgn[chain[id]] + cnt[chain[id]] - 1;
    if (ord[id] < cnt[chain[id]]) aux2 = query(st, dr);
    if (aux > aux2) mx = aux;
    else mx = aux2;
    if (stotal-aux-aux2-a[id] > mx) mx = stotal - aux-aux2-a[id];
    return mx;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ifstream cin ("rafaela.in");
    ofstream cout ("rafaela.out");
    cin >> n >> m;
    for (int i=1, x, y; i<n; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i=1; i<=n; i++) cin >> a[i], stotal += a[i];
    getsz(1, -1);
    start_node[1] = 1;
    hld(1, -1);
    for (int i=1, nr, id; i<=m; i++){
        /*
        cout << i << ":\n";
        for (int j=1; j<=n; j++){
            cout << j << ' ' << sum_subarb[j] << ' ' << query(bgn[chain[j]] + ord[j]-1, bgn[chain[j]]+cnt[chain[j]]-1) << '\n';
            if (!S[j].size()) continue;
            cout << "multiset: ";
            for (auto it: S[j]) cout << it << ' ';
            cout << '\n';
        }
        */
        char c;
        cin >> c;
        if (c == 'U'){
            cin >> nr >> id;
            update(id, nr);
            a[id] += nr; stotal += nr;
        }
        else{
            cin >> id;
            cout << ask(id) << '\n';
        }
    }
    return 0;
}