Cod sursa(job #1321717)

Utilizator retrogradLucian Bicsi retrograd Data 19 ianuarie 2015 14:40:48
Problema SequenceQuery Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<fstream>
#include<vector>

#define MAXN 100001

using namespace std;
typedef int var;

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

var TREE[3*MAXN];

vector<var> G[MAXN];
vector<var> L;
vector<var> RANK[MAXN];
var BEG[MAXN], END[MAXN];
bool VIZ[MAXN];


var n, m;

void dfs(var node, var r) {
    VIZ[node] = 1;
    L.push_back(node);
    RANK[r].push_back(node);
    BEG[node] = L.size() - 1;
    for(; !G[node].empty(); G[node].pop_back()) {
        if(!VIZ[G[node].back()]) {
            dfs(G[node].back(), r+1);
        }
    }
    END[node] = L.size() - 1;
}

void addSum(var node, var b, var e, var l, var r, var s) {
    if(l<=b && r>=e) {TREE[node] += s; return;}
    if(e<l || b>r) return;
    var m = (b+e)/2;
    addSum(node*2, b, m, l, r, s);
    addSum(node*2+1, m+1, e, l, r, s);
}

var findsum(var node, var b, var e, var i) {
    if(b == e) return TREE[node];
    var m = (b+e)/2;
    if(m >= i) return findsum(node*2, b, m, i);
    else return findsum(node*2+1, m+1, e, i);
}



void read() {
    fin>>n>>m;
    var a, b;
    for(var i=1; i<n; i++) {
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1, 0);
}

int main() {
    L.push_back(0);
    read();
    var type, t, s;
    while(m--) {
        fin>>type;
        if(type == 1) {
            fin>>t>>s;
            addSum(1, 1, n, BEG[t], END[t], s);
        }
        else {
            fin>>s;
            fout<<checksum(1, 1, n, s, 0)<<'\n';
        }
    }
    return 0;
}