Pagini recente » Cod sursa (job #751551) | Cod sursa (job #1737879) | Cod sursa (job #1773587) | Cod sursa (job #1640693) | Cod sursa (job #1477940)
#include <fstream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#define fi first
#define se second
#define mp make_pair
#define pe pair<int, int>
using namespace std;
ifstream fin("arbore.in");
ofstream fout("arbore.out");
const int MAX_N = 100100;
const int MOD = 100003;
const int MAX_R = 320;
vector<int> A[MAX_N];
int v[MAX_N];
unordered_multiset<int> M[MAX_R];
int lz[MAX_R];
int n, r;
int ti[MAX_N];
int to[MAX_N];
int t;
void dfs(int nod) {
ti[nod] = ++t;
for(auto it : A[nod]) {
A[it].erase(find(A[it].begin(), A[it].end(), nod));
dfs(it);
}
to[nod] = t;
}
void update(int st, int dr, int val) {
for(int i = 0; i <= r; i++) {
if(st > (i + 1) * r) {
continue;
}
else if(i * r > st && (i + 1) * r <= dr) {
lz[i] += val;
}
else {
for(int j = i * r + 1; j <= min((i + 1) * r, n); j++) {
if(j >= st && j <= dr) {
M[i].erase(M[i].find(v[j]));
v[j] += val;
M[i].insert(v[j]);
}
}
}
}
}
int query(int s) {
for(int i = 0; i <= r; i++) {
auto it = M[i].find(s - lz[i]);
if(it != M[i].end()) {
for(int j = i * r; j <= min((i + 1) * r, n); j++) {
if(v[j] == s - lz[i]) {
return j;
}
}
}
}
return -1;
}
int main() {
int m;
fin >> n >> m;
r = sqrt(n);
for(int i = 1; i < n; i++) {
int a, b;
fin >> a >> b;
A[a].push_back(b);
A[b].push_back(a);
}
dfs(1);
for(int i = 0; i <= r; i++) {
for(int j = i * r + 1; j <= min( (i + 1) * r, n); j++) {
M[i].insert(0);
}
}
for(int i = 1; i <= m; i++) {
int t;
fin >> t;
if(t == 1) {
int p, s;
fin >> p >> s;
update(ti[p], to[p], s);
}
else {
int s;
fin >> s;
fout << query(s) << '\n';
}
}
return 0;
}