Pagini recente » Cod sursa (job #899317) | Cod sursa (job #1397602) | Cod sursa (job #1874319) | Cod sursa (job #449420) | Cod sursa (job #1722173)
#include<cstdio>
#include<vector>
#include<bitset>
#define SIZE 330
#define MAXN 100010
using namespace std;
vector<int> g[MAXN];
bitset<MAXN> possible[SIZE+5];
int n,m,first[MAXN],last[MAXN],order[MAXN],current=0;
int add[MAXN],v[MAXN];
void DFS(int node,int father){
int i;
current++;
order[current]=node;
first[node]=current;
for(i=0;i<g[node].size();i++)
if(g[node][i]!=father)
DFS(g[node][i],node);
last[node]=current;
}
void Update(int left,int right,int value){
int bucket,i;
bucket=(left-1)/SIZE+1;
for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
possible[bucket][v[i]]=0;
for(i=left;i<=right&&i<=bucket*SIZE;i++)
v[i]+=value;
for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
possible[bucket][v[i]]=1;
if(bucket==right/SIZE+1)
return;
bucket++;
if(bucket!=right/SIZE)
for(bucket;bucket*SIZE<=right;bucket++)
add[bucket]+=value;
for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
possible[bucket][v[i]]=0;
for(i=(bucket-1)*SIZE+1;i<=right&&i<bucket*SIZE;i++)
v[i]+=value;
for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
possible[bucket][v[i]]=1;
}
int Query(int value){
int bucket,i;
for(bucket=1;bucket*SIZE<=n;bucket++)
if(value>=add[bucket]&&possible[bucket][value-add[bucket]])
for(i=(bucket-1)*SIZE+1;i<=bucket*SIZE;i++)
if(v[i]+add[bucket]==value)
return order[i];
for(i=(bucket-1)*SIZE+1;i<=n;i++)
if(v[i]+add[bucket]==value)
return order[i];
return -1;
}
int main(){
freopen("arbore.in","r",stdin);
freopen("arbore.out","w",stdout);
int i,a,b,type,p,s;
scanf("%d%d",&n,&m);
for(i=1;i<n;i++){
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
DFS(1,0);
for(i=1;i<=m;i++){
scanf("%d",&type);
if(type==1){
scanf("%d%d",&p,&s);
Update(first[p],last[p],s);
}
else{
scanf("%d",&s);
printf("%d\n",Query(s));
}
}
return 0;
}