Pagini recente » Cod sursa (job #1770495) | Cod sursa (job #2575621) | Cod sursa (job #1805551) | Cod sursa (job #1746132) | Cod sursa (job #2766920)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("arbore.in");
ofstream fout("arbore.out");
const int MAXN = 1e5;
const int MAXV = 1e6;
const int B = 320;
int n, q, timer = -1, ver[MAXN], l[MAXN], r[MAXN], v[MAXN];
vector<int> G[MAXN];
struct bucket {
int offset;
bitset<1 + MAXV> ap;
} a[B];
int get_bucket(int index) {
return index / B;
}
void dfs(int u, int p) {
ver[++timer] = u;
l[u] = timer;
for (int v : G[u])
if (v != p)
dfs(v, u);
r[u] = timer;
}
void update(int st, int dr, int bucket_index, int s) {
for (int i = bucket_index * B; i < min(n, (bucket_index + 1) * B); ++i)
a[bucket_index].ap[v[i]] = false;
for (int i = st; i <= dr; ++i)
v[i] += s;
for (int i = bucket_index * B; i < min(n, (bucket_index + 1) * B); ++i)
a[bucket_index].ap[v[i]] = true;
}
int main() {
fin >> n >> q;
int cnt_buckets = 0;
for (int i = 0; i < n; i += B) {
a[cnt_buckets].ap[0] = true;
a[cnt_buckets].offset = 0;
++cnt_buckets;
}
for (int e = 1; e < n; ++e) {
int u, v;
fin >> u >> v;
--u, --v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
dfs(0, -1);
for (int i = 0; i < q; ++i) {
int t;
fin >> t;
if (t == 1) {
int v, s;
fin >> v >> s;
--v;
int st = l[v], dr = r[v], curr_bucket = get_bucket(l[v]);
if (st % B) {
++curr_bucket;
update(st, min(dr, curr_bucket * B - 1), curr_bucket - 1, s);
}
while ((curr_bucket + 1) * B - 1 <= dr)
a[curr_bucket++].offset += s;
st = curr_bucket * B;
if (st <= dr)
update(st, dr, curr_bucket, s);
} else {
int s;
fin >> s;
int ans = -2;
for (int b = 0; b < cnt_buckets; ++b)
if (s >= a[b].offset && a[b].ap[s - a[b].offset]) {
for (int j = b * B; ; ++j)
if (v[j] + a[b].offset == s) {
ans = ver[j];
break;
}
break;
}
fout << ans + 1 << '\n';
}
}
fin.close();
fout.close();
return 0;
}