Cod sursă (job #144142)

/*
 * Vlad Ionescu - Universitatea Politehnica Bucuresti
 * Rafaela - update: O(logN), query: O(nr_fii * logN)
 */
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define maxn 200100
#define LSB(x) (x&(-x))

int N, Q;
vector<int> G[maxn];

int no_of_mans, euler_time;
int initial[maxn], viz[maxn], father[maxn], first_app[maxn], last_app[maxn], aib[maxn];

void euler(int node, int fath) {
    viz[node] = 1;
    father[node] = fath;

    euler_time ++;
    first_app[node] = euler_time;

    for(int i=0; i<G[node].size(); i++) {
        if(!viz[ G[node][i] ]) {
            euler(G[node][i], node);
        }
    }

    last_app[node] = euler_time;
}

void update_aib(int pos, int value) {
    while(pos <= N) {
        aib[pos] += value;

        pos += LSB(pos);
    }
}

int query_aib(int pos) {
    int ret = 0;

    while(pos) {
        ret += aib[pos];

        pos -= LSB(pos);
    }

    return ret;
}

int query_aib_limits(int start, int finish) {
    return query_aib(finish) - query_aib(start - 1);
}

void update(int node, int value) {
    update_aib(first_app[node], value);
}

int query(int node) {
    int ret = 0;
    int sum = 0;
    int x;

    for(int i=0; i<G[node].size(); i++) {
        if(G[node][i] != father[node]) {
            x = query_aib_limits(first_app[ G[node][i] ], last_app[ G[node][i] ]);

            ret = max(ret, x);
            sum += x;
        }
    }

    ret = max(ret, no_of_mans - initial[node] - sum);

    return ret;
}

int main() {
    fstream f1, f2;
    int x, y;
    char code;

    f1.open("rafaela.in", ios::in);
    f2.open("rafaela.out", ios::out);

    f1 >> N >> Q;

    for(int i=1; i<N; i++) {
        f1 >> x >> y;

        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i=1; i<=N; i++) {
        f1 >> initial[i];

        no_of_mans += initial[i];
    }

    euler(1, 0);

    for(int i=1; i<=N; i++) {
        update_aib(first_app[i], initial[i]);
    }

    for(int i=0; i<Q; i++) {
        f1 >> code;

        if(code == 'Q') {
            f1 >> x;

            f2 << query(x) << '\n';
        }
        else if(code == 'U') {
            f1 >> x;
            f1 >> y;
            no_of_mans += x;
            initial[y] += x;
            update(y, x);
		}
    }

    f1.close();
    f2.close();

    return 0;
}