Pagini recente » Cod sursa (job #772087) | Cod sursa (job #2892227) | Cod sursa (job #1515690) | Cod sursa (job #145955) | Cod sursa (job #2396924)
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;
ifstream fin ("arbore.in");
ofstream fout("arbore.out");
int n,m,rad,cnt,tip,s,i,j,p,k,ADD[5000],A[100001],v[200001],x;
int st[100001],dr[100001]; /// a[i],b[i] capetele subarborilor cu radacina in i
int bst,bdr; ///buc din care facc parte capetele
bitset <100001> f;
vector <int> l[100001];
bitset <100001> F[5001];
void dfs(int nod){
f[nod]=1;
v[++k]=nod;
st[nod]=k;
for(int i=0;i<l[nod].size();i++)
if( f[l[nod][i]]==0 )
dfs(l[nod][i]);
///v[++k]=nod;
dr[nod]=k;
}
int main(){
fin>>n>>m;
for(k=1;k<n;k++){
fin>>i>>j;
l[i].push_back(j);
l[j].push_back(i);
}
k=0;
dfs(1);
/**
for(i=1;i<=n;i++)
cout<<v[i]<<" ";
cout<<"\n";
*/
rad=sqrt(n);
cnt=(n)/rad+(n%rad!=0);
for(;m;m--){
///cout<<"\noperatia "<<++x<<"\n";
fin>>tip;
if(tip==1){
fin>>p>>s;
bst=st[p]/rad+(st[p]%rad!=0);
bdr=dr[p]/rad+(dr[p]%rad!=0);
///cout<<st[p]<<" "<<bst<<" | "<<dr[p]<<" "<<bdr<<"\n";
if(bst==bdr){
for(i=st[p];i<=dr[p];i++)
A[ v[i] ]+=s;
F[bst].reset();
for(i=(bst-1)*rad+1;i<=min(bst*rad,n);i++)
F[bst][A[ v[i] ]]=1;
}else{
for(i=st[p];i<=bst*rad;i++)
A[ v[i] ]+=s;
F[bst].reset();
for(i=(bst-1)*rad+1;i<=min(bst*rad,n);i++)
F[bst][A[ v[i] ]]=1;
for(i=(bdr-1)*rad+1;i<=dr[p];i++)
A[ v[i] ]+=s;
F[bdr].reset();
for(i=(bdr-1)*rad+1;i<=min(bdr*rad,2*n);i++)
F[bdr][A[ v[i] ]]=1;
for(i=bst+1;i<bdr;i++){
ADD[i]+=s;
///cout<<"adaug "<<s<<"in bucket-ul "<<i<<"\n";
}
}
}else{
fin>>s;
///fout<<m<<" ";
for(i=1;i<=cnt;i++)
if(s-ADD[i]>0)
if(F[i][s-ADD[i]]==1){
for(j=(i-1)*rad+1;j<=min(i*rad,n);j++){
if(A[j]+ADD[i]==s){
cout<<A[j]<<" "<<ADD[i]<<"\n";
fout<<v[j]<<"\n";
break;
}
}
break;
}
if(i==cnt+1)
fout<<-1<<"\n";
}
}
return 0;
}