Pagini recente » Cod sursa (job #3182850) | Cod sursa (job #3236090) | Cod sursa (job #2533240) | Cod sursa (job #2248389) | Cod sursa (job #1018395)
#include<fstream>
#include<bitset>
#include<vector>
#include<cmath>
#define NMAX 100002
#define SQRT 320
using namespace std;
ifstream fin("arbore.in");
ofstream fout("arbore.out");
vector<int> G[NMAX];
int n,m,lin[NMAX],first[NMAX],last[NMAX],k,node_val[NMAX];
bool use[NMAX];
bitset<1000001> values[SQRT];
struct piece
{
int left,right,common;
}v[SQRT];
void read()
{
fin>>n>>m;
for(int i=1,x,y;i<n;i++)
{
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
/*
void Affis(string fis)
{
ifstream fout1(fis);
for(int i = 1; i <= n; i++)
fout1 << i << " ";
fout1.close();
}
*/
void DFS(int nod)
{
use[nod]=1;
lin[++k]=nod;
first[nod]=k;
for(size_t i=0;i<G[nod].size();i++)
if(!use[G[nod][i]])
DFS(G[nod][i]);
last[nod]=k;
}
void split()
{
k=0;
for(int i=1,L=(int)sqrtl(n);i<=n;i+=L)
{
v[++k].left=i;
v[k].right=min(i+L-1,n);
values[k][0]=1;
}
}
void update(int left,int right,short add)
{
for(int i=1;i<=k;i++)
{
if(v[i].left>right)
return;
if(v[i].right<left)
continue;
if(left<=v[i].left && v[i].right<=right)
{
v[i].common+=add;
continue;
}
for(int j=v[i].left;j<=v[i].right;j++)
{
values[i][node_val[j]]=0;
node_val[j]+=v[i].common;
if(left<=j && right>=j)
node_val[j]+=add;
}
for(int j=v[i].left;j<=v[i].right;j++)
values[i][node_val[j]]=1;
v[i].common=0;
}
}
int query(int sum)
{
for(int i=1,Value;i<=k;i++)
{
Value=sum-v[i].common;
if(v[i].common<=sum && values[i][Value])
for(int j=v[i].left;j<=v[i].right;j++)
if(Value==node_val[j])
return lin[j];
}
return -1;
}
void solve()
{
DFS(1);
split();
for(int a,b,c;m;m--)
{
fin>>a>>b;
if(a==1)
{
fin>>c;
update(first[b],last[b],c);
continue;
}
fout<<query(b)<<'\n';
}
}
int main()
{
read();
solve();
return 0;
}