Pagini recente » Cod sursa (job #825594) | Cod sursa (job #1600456) | Cod sursa (job #1466258) | Cod sursa (job #856428) | Cod sursa (job #2766922)
#include <bits/stdc++.h>
using namespace std;
struct InParser {
FILE * fin;
char * buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
InParser(const char * nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser & operator >> (int & n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser 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) {
int nxt = min(n, (bucket_index + 1) * B);
for (int i = bucket_index * B; i < nxt; ++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 < nxt; ++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';
}
}
fout.close();
return 0;
}