Pagini recente » Cod sursa (job #1189991) | Cod sursa (job #1522574) | Cod sursa (job #1999838) | Cod sursa (job #2073742) | Cod sursa (job #1369989)
#include<fstream>
#include<vector>
using namespace std;
typedef int var;
ifstream fin("arbore.in");
ofstream fout("arbore.out");
#define MAXN 200005
var TREE[MAXN];
var tm = 0;
var BEG[MAXN], END[MAXN];
vector<var> G[MAXN], A[MAXN];
var n;
inline var zeros(const var &v) {
return v & (-v);
}
void add(var ind, var val) {
for(; ind<=tm; ind+=zeros(ind)) {
TREE[ind] += val;
}
}
var query(var ind) {
var sum = 0;
for(; ind; ind-=zeros(ind)) {
sum += TREE[ind];
}
return sum;
}
void linear(var node) {
BEG[node] = ++tm;
for(auto vec : G[node]) {
if(!BEG[vec]) {
A[node].push_back(vec);
linear(vec);
}
}
END[node] = ++tm;
}
var solve(var node, var sum) {
var q = query(BEG[node]);
if(q == sum) {
return node;
}
if(q > sum) {
return -1;
}
for(auto vec : A[node]) {
var rez = solve(vec, sum);
if(rez != -1) {
return rez;
}
}
return -1;
}
int main() {
var m, a, b, type, sum;
fin>>n>>m;
for(var i=2; i<=n; i++) {
fin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
linear(1);
while(m--) {
fin>>type;
if(type == 1) {
fin>>a>>sum;
add(BEG[a], sum);
add(END[a], -sum);
} else {
var i;
fin>>sum;
fout<<solve(1, sum)<<'\n';
}
}
linear(1);
}