Pagini recente » Cod sursa (job #1323882) | Cod sursa (job #2570197) | Cod sursa (job #1175390) | Cod sursa (job #38966) | Cod sursa (job #846475)
Cod sursa(job #846475)
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int N = 100011;
const int VMAX = 1000001;
const int SIZE = 320;
int nr, n, m, conv[N], cd[N], ord[N], pl[SIZE], val[N];
vector<int> v[N];
bool ver[N];
map<int, int> h[SIZE];
void df(int nod) {
ver[nod] = 1;
conv[nod] = nr;
ord[nr] = nod;
++nr;
for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
if(!ver[*it])
df(*it);
cd[nod] = nr - 1;
}
void make() {
for(int i = 0; i < nr; i++) {
h[i/SIZE][0]++;
}
}
void add(int cs, int cd, int va) {
int i = cs;
while(i <= cd && i % SIZE != 0) {
int b = i / SIZE;
h[b][val[i]]--;
val[i] += va;
h[b][val[i]]++;
++i;
}
while(i + SIZE - 1 <= cd) {
int b = i / SIZE;
pl[b] += va;
i += SIZE;
}
while(i <= cd) {
int b = i / SIZE;
h[b][val[i]]--;
val[i] += va;
h[b][val[i]]++;
++i;
}
}
int query(int sum) {
for(int i = 0, j = 0, s2; i < nr; i += SIZE, ++j) {
s2 = sum - pl[j];
if(s2 < 0)
continue;
if(h[j][s2]) {
for(int k = i; k < i + SIZE; ++k)
if(val[k] == s2)
return ord[k];
}
}
return -1;
}
int main() {
int i, a, b, op;
freopen("arbore.in", "r", stdin);
freopen("arbore.out", "w", stdout);
cin >> n >> m;
for(i = 1; i != n; ++i) {
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
df(1);
make();
for(i = 1; i<=n; ++i) {
scanf("%d", &op);
if(op == 1) {
scanf("%d%d", &a, &b);
add(conv[a], cd[a], b);
}
else {
scanf("%d", &b);
printf("%d\n", query(b));
}
}
return 0;
}