Pagini recente » Cod sursa (job #1740871) | Cod sursa (job #829912) | Cod sursa (job #2860924) | Cod sursa (job #463916) | Cod sursa (job #1332181)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("arbore.in");
ofstream g ("arbore.out");
const int NMAX = 100000 + 1;
int n, m;
int poz, sol;
int v[NMAX];
int stanga[NMAX], dreapta[NMAX];
vector <int> graf[NMAX];
int arb_sum[2 * 4 * NMAX], arb_max[2 * 4 * NMAX];
void citeste() {
int a, b;
f >> n >> m;
for (int i = 1; i < n; i++) {
f >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
}
void DFS(int nod, int tata) {
v[++poz] = nod;
stanga[nod] = poz;
int l = graf[nod].size();
for (int i = 0; i < l; i++)
if (graf[nod][i] != tata) DFS(graf[nod][i], nod);
v[++poz] = nod;
dreapta[nod] = poz;
}
void update(int nod, int st, int dr, int x, int val) {
if (stanga[x] <= st && dr <= dreapta[x]) {
arb_sum[nod] += val;
arb_max[nod] = arb_sum[nod] + max(arb_max[2 * nod], arb_max[2 * nod + 1]);
return;
}
int m = (st + dr) / 2;
if (stanga[x] <= m) update(2 * nod, st, m, x, val);
if (dreapta[x] > m) update(2 * nod + 1, m + 1, dr, x, val);
arb_max[nod] = arb_sum[nod] + max(arb_max[2 * nod], arb_max[2 * nod + 1]);
}
void query(int nod, int st, int dr, int suma) {
if (sol > 0) return;
if (arb_sum[nod] == suma) {
sol = v[st];
return;
}
if (st < dr && arb_sum[nod] < suma && arb_max[nod] >= suma) {
int m = (st + dr) / 2;
query(2 * nod, st, m, suma - arb_sum[nod]);
query(2 * nod + 1, m + 1, dr, suma - arb_sum[nod]);
}
}
void rezolva() {
int tip, p, s;
for (int i = 1; i <= m; i++) {
f >> tip;
if (tip == 1) {
f >> p >> s;
update(1, 1, poz, p, s);
}
else {
sol = -1;
f >> s;
query(1, 1, poz, s);
g << sol << '\n';
}
}
}
int main() {
citeste();
DFS(1, 0);
//for (int i = 1; i <= poz; i++) cout << v[i] << ' ';
rezolva();
}