Pagini recente » Cod sursa (job #1032517) | Cod sursa (job #2727968) | Cod sursa (job #2016219) | Cod sursa (job #1113684) | Cod sursa (job #1369854)
#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];
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]) {
linear(vec);
}
}
END[node] = ++tm;
}
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;
for(i=1; i<=n; i++) {
var si = query(BEG[i]);
if(si == sum) {
fout<<i<<'\n';
break;
}
}
if(i>n) {
fout<<"-1\n";
}
}
}
linear(1);
}