Cod sursa(job #1369854)

Utilizator retrogradLucian Bicsi retrograd Data 3 martie 2015 11:48:17
Problema Arbore Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 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];
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]) {
            linear(vec);
        }
    }
    END[node] = ++tm;
}

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;
            for(i=1; i<=n; i++) {
                var si = query(BEG[i]);
                if(si == sum) {
                    fout<<i<<'\n';
                    break;
                }
            }
            if(i>n) {
                fout<<"-1\n";
            }
        }
    }
    linear(1);
}