Cod sursa(job #1369948)

Utilizator retrogradLucian Bicsi retrograd Data 3 martie 2015 12:22:16
Problema Arbore Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<fstream>
#include<vector>

using namespace std;

typedef int var;
ifstream fin("arbore.in");
ofstream fout("arbore.out");

#define MAXN 200005
var TREE[MAXN];
var tm = 0;
var BEG[MAXN], END[MAXN];
vector<var> G[MAXN], A[MAXN];
var n;

inline var zeros(const var &v) {
    return v & (-v);
}

void add(var ind, var val) {
    for(; ind<=tm; ind+=zeros(ind)) {
        TREE[ind] += val;
    }
}

var query(var ind) {
    var sum = 0;
    for(; ind; ind-=zeros(ind)) {
        sum += TREE[ind];
    }
    return sum;
}


void linear(var node) {
    BEG[node] = ++tm;
    for(auto vec : G[node]) {
        if(!BEG[vec]) {
            A[node].push_back(vec);
            linear(vec);
        }
    }
    END[node] = ++tm;
}

var solve(var node, var sum) {
    var q = query(BEG[node]);
    if(q == sum) {
        return node;
    }
    if(q > sum) {
        return -1;
    }
    for(auto vec : A[node]) {
        var rez = solve(vec, sum);
        if(rez != -1) {
            return rez;
        }
    }

    return -1;
}

int main() {
    var m, a, b, type, sum;
    fin>>n>>m;
    for(var i=2; i<=n; i++) {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    linear(1);

    while(m--) {
        fin>>type;
        if(type == 1) {
            fin>>a>>sum;
            add(BEG[a], sum);
            add(END[a], -sum);
        } else {
            var i;
            fin>>sum;
            fout<<solve(1, sum)<<'\n';
        }
    }
    linear(1);
}