Pagini recente » Cod sursa (job #1875176) | Cod sursa (job #275040) | Cod sursa (job #1694769) | Cod sursa (job #1651884) | Cod sursa (job #910664)
Cod sursa(job #910664)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("arbore.in");
ofstream g("arbore.out");
#define nmax 100005
#define ll long long
int n, m, sz, P[nmax], U[nmax], sum[nmax], sum2[nmax];
bool viz[nmax];
vector<int> gf[nmax];
void citeste(){
f >> n >> m;
int x, y;
for(int i=1; i<n; ++i){
f >> x >> y;
gf[x].push_back(y);
gf[y].push_back(x);
}
}
void dfs(int nod){
viz[nod] =1;
P[nod] = ++sz;
for(int i=0; i<gf[nod].size(); ++i){
int vc = gf[nod][i];
if (viz[vc] == 0){
dfs(vc);
}
}
U[nod] = sz;
}
void rezolva(){
// o(1) pe uptadet si o(n) pe query cu smenul lui mars
dfs(1);
//for(int i=1; i<=n; ++i) cout << P[i] << " " << U[i] << "\n";
int tip, p, s;
for(int j=1; j<=m; ++j){
f >> tip;
if (tip == 1){
f >> p >> s;
sum[P[p]] += s;
sum[U[p]+1] -= s;
}else {
f >> s;
for(int i=1; i<=n; ++i) sum2[i] = sum2[i-1] + sum[i];
int ok = 0;// pp ca nu e;
for(int i=1; i<=n; ++i){
if (sum2[ P[i] ] == s){
ok = 1;
g << i << "\n";
break;
}
}
if (ok==0){
g << -1 <<"\n";
}
}
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}