Pagini recente » Cod sursa (job #2660632) | Cod sursa (job #2489279) | Cod sursa (job #2052369) | Cod sursa (job #861156) | Cod sursa (job #879857)
Cod sursa(job #879857)
#include <fstream>
#include <vector>
#define nmax 100100
using namespace std;
int N,M,Answer,A[nmax],B[nmax];
bool viz[nmax];
vector <int> G[nmax],V;
int S[6*nmax],Max[6*nmax];
bool Query(int Nod,int Left,int Right,int Val) {
if((Val-=S[Nod]) == 0) {
Answer=V[Left-1];
return 1;
}
int Mid=(Left+Right)>>1,sw=0;
if(Left!=Right && Val>0 && Max[Nod]-S[Nod]>=Val)
if((sw=Query(2*Nod,Left,Mid,Val))==0)
sw=Query(2*Nod+1,Mid+1,Right,Val);
Val+=S[Nod];
return sw;
}
void Update(int Nod,int Left,int Right,int Angajat,int Val) {
if(A[Angajat]<=Left && Right<= B[Angajat])
S[Nod]+=Val;
else {
int Mid=(Left+Right)>>1;
if(A[Angajat]<=Mid) Update(2*Nod,Left,Mid,Angajat,Val);
if(Mid<B[Angajat]) Update(2*Nod+1,Mid+1,Right,Angajat,Val);
}
Max[Nod]=S[Nod]+max(Max[2*Nod],Max[2*Nod+1]);
}
void DFS(int Nod) {
viz[Nod]=1;
V.push_back(Nod);
A[Nod]=V.size();
for(int i=0;i<G[Nod].size();i++)
if(!viz[G[Nod][i]])
DFS(G[Nod][i]);
B[Nod]=V.size();
}
void read(ifstream & in) {
int i,x,y;
in>>N>>M;
for(i=1;i<N;i++) {
in>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
int main() {
int tip,Angajat,Val;
ifstream in("arbore.in");
ofstream out("arbore.out");
read(in);
DFS(1);
while(M--) {
in>>tip;
if(tip==1) {
in>>Angajat>>Val;
Update(1,1,N,Angajat,Val);
}
else {
in>>Val;
if(Query(1,1,N,Val))
out<<Answer<<'\n';
else
out<<"-1\n";
}
}
in.close();
out.close();
return 0;
}