Cod sursa(job #1133381)

Utilizator deneoAdrian Craciun deneo Data 4 martie 2014 20:30:58
Problema Arbore Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 100100;

int n, q, p, start[MAXN], last[MAXN], pos_to_nod[MAXN], elem[MAXN];
vector<int> graf[MAXN];

void dfs (int nod, int dad) {
    start[nod] = ++p;
    pos_to_nod[p] = nod;

    for (int i = 0; i < (int)graf[nod].size(); ++i) {
        int node = graf[nod][i];
        if (node != dad)
            dfs (node, nod);
    }

    last[nod] = p;
}

void update (int start, int last, int s) {
    for (int i = start; i <= last; ++i)
        elem[i] += s;
}

int query (int s) {
    for(int i = 1; i <= n; ++i)
        if (elem[i] == s)
            return pos_to_nod[i];
    return -1;
}


int main() {
    fin >> n >> q;

    for (int i = 1; i < n; ++i) {
        int a, b; fin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    dfs (1, 0);

    for (int i = 1; i <= q; ++i) {
        int type; fin >> type;

        if (type == 1) {
            int nod, s; fin >> nod >> s;
            update (start[nod], last[nod], s);
        }
        else {
            int s; fin >> s;
            fout << query(s) << "\n";
        }
    }

    return 0;
}