Pagini recente » Cod sursa (job #1344561) | Monitorul de evaluare | Cod sursa (job #2068664) | Cod sursa (job #1344557) | Cod sursa (job #3305689)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("arbore.in");
ofstream out("arbore.out");
const int nmax = 1e5;
int n, nrq, value[nmax + 2], type, a, b;
int preorder[nmax + 2], leaffsub[nmax + 2];
int actually[nmax + 2];
vector <int> muchii[nmax + 2];
void dfs(int node, int father){
preorder[node] = (++preorder[0]);
actually[preorder[0]] = node;
leaffsub[node] = preorder[0];
for(auto nxt : muchii[node]){
if(nxt != father){
dfs(nxt, node);
leaffsub[node] = max(leaffsub[node], leaffsub[nxt]);
}
}
}
int mars[nmax + 2];
int main(){
in>>n>>nrq;
for(int i = 1; i <= n - 1; i++){
in>>a>>b;
muchii[a].push_back(b);
muchii[b].push_back(a);
}
dfs(1, 0);
for(int i = 1; i <= nrq; i++){
in>>type;
if(type == 1){
in>>a>>b;
mars[preorder[a]] += b;
mars[leaffsub[a] + 1] -= b;
}else{
in>>a;
int sum = 0, flagg = 0;
for(int it = 1; it <= n; it++){
sum += mars[it];
if(sum == a){
out<<actually[it]<<"\n";
flagg = 1; break;
}
}
if(!flagg){ out<<"-1\n"; }
}
}
return 0;
}