Pagini recente » Cod sursa (job #1917244) | Cod sursa (job #2116075) | Cod sursa (job #1636443) | Cod sursa (job #2021275) | Cod sursa (job #1133381)
#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;
}