Pagini recente » Cod sursa (job #2861636) | Cod sursa (job #1633231) | Cod sursa (job #1632691) | Cod sursa (job #1437985) | Cod sursa (job #3222920)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("arbore.in");
ofstream fout("arbore.out");
const int Nmax=1e5+5;
int n;
int SQRT;
int a[Nmax];
int ad[355];
multiset<int> f[355];
int sz[Nmax],pos[Nmax];
vector<int> v[Nmax];
vector<int> lin;
void dfs(int nod,int prev)
{
sz[nod]=1;
lin.push_back(nod);
pos[nod]=lin.size()-1;
for(int u:v[nod])
{
if(u!=prev)
{
dfs(u,nod);
sz[nod]+=sz[u];
}
}
return;
}
void init()
{
for(int i=0;i<n;i++)
{
int B=i/SQRT;
f[B].insert(0);
}
return;
}
void update(int l,int r,int s)
{
int lB=l/SQRT,rB=r/SQRT;
if(lB==rB)
{
for(int i=l;i<=r;i++)
{
f[lB].erase(f[lB].find(a[i]));
a[i]+=s;
f[lB].insert(a[i]);
}
return;
}
for(int i=l;i<(lB+1)*SQRT;i++)
{
f[lB].erase(f[lB].find(a[i]));
a[i]+=s;
f[lB].insert(a[i]);
}
for(int i=r;i>=rB*SQRT;i--)
{
f[rB].erase(f[rB].find(a[i]));
a[i]+=s;
f[rB].insert(a[i]);
}
for(int b=lB+1;b<=rB-1;b++)
{
ad[b]+=s;
}
}
int query(int val)
{
int goodB=-1;
for(int b=0;b<=(n-1)/SQRT;b++)
{
if(ad[b]>val) continue;
int need=val-ad[b];
if(f[b].find(need)!=f[b].end())
{
goodB=b;
break;
}
}
if(goodB==-1) return -1;
for(int i=goodB*SQRT;i<(goodB+1)*SQRT;i++)
{
if(a[i]==val-ad[goodB]) return lin[i];
}
}
int main()
{
int m;
fin>>n>>m;
SQRT=sqrt(n);
init();
for(int i=1;i<n;i++)
{
int x,y;
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
while(m--)
{
int c;
fin>>c;
if(c==1)
{
int nod,s;
fin>>nod>>s;
update(pos[nod],pos[nod]+sz[nod]-1,s);
}
else
{
int val;
fin>>val;
fout<<query(val)<<'\n';
}
}
return 0;
}