Pagini recente » Cod sursa (job #1502149) | Cod sursa (job #492942) | Cod sursa (job #1377551) | Cod sursa (job #1917295) | Cod sursa (job #3190808)
#include <bits/stdc++.h>
using namespace std;
string file = "arbore";
ifstream fin(file + ".in");
ofstream fout(file + ".out");
int n, m;
vector <int> g[100001];
int v[300001], sz, first[100001], last[100001];
unordered_map <long long, int> M[600];
long long add[600];
const int root = 550;
void dfs(int node = 1, int p = -1) {
first[node] = last[node] = ++sz;
for (auto &i : g[node])
if (i != p) {
dfs(i, node);
last[node] = ++sz;
}
}
int main() {
fin >> n >> m;
for (int i = 1; i < n; i++) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs();
for (int i = 1; i <= sz; i++)
M[i / root][0]++;
for (int i = 1; i <= m; i++) {
int type;
fin >> type;
if (type == 1) {
int p, s;
fin >> p >> s;
if (last[p] - first[p] + 1 <= 2 * root) {
for (int j = first[p]; j <= last[p]; j++) {
M[j / root][v[j]]--;
v[j] += s;
M[j / root][v[j]]++;
}
}
else {
int x, y;
x = first[p];
y = last[p];
int aux = (first[p] / root + 1) * root;
for (int j = first[p]; j < aux; j++) {
M[j / root][v[j]]--;
v[j] += s;
M[j / root][v[j]]++;
}
x = aux;
y -= y % root - 1;
for (int j = last[p]; j > y; j--) {
M[j / root][v[j]]--;
v[j] += s;
M[j / root][v[j]]++;
}
for (int j = x; j <= y; j += root)
add[j / root] += s;
}
}
else {
int s;
fin >> s;
int aux = 0;
for (int j = 1; j <= sz; j = (j / root + 1) * root) {
if (M[j / root][s - add[j / root]]) {
aux = j;
break;
}
}
if (aux == 0) {
fout << "-1\n";
continue;
}
for (int j = aux; j < (aux / root + 1) * root; j++)
if (v[j] + add[j / root] == s) {
fout << j << '\n';
break;
}
}
}
return 0;
}