Pagini recente » Cod sursa (job #271823) | Cod sursa (job #2838796) | Cod sursa (job #358036) | Cod sursa (job #1935510) | Cod sursa (job #3196203)
#include <fstream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <map>
#include <cmath>
using namespace std;
ifstream fin ("arbore.in");
ofstream fout("arbore.out");
int n,m,x,T,y,i,Q,k,p,s,rad,nrb,I[200003],first[100003],last[100003],V[200003],S[603];
vector <int> L[100003];
unordered_map <int,int> F[603];
inline int bucket(int x){ return x/rad+(x%rad!=0);}
inline int bucket_start(int x){ return (x-1)*rad+1;}
void dfs(int x,int t)
{
first[x]=++k;
I[k]=x;
for(auto j:L[x])
if(j!=t)
dfs(j,x);
last[x]=++k;
I[k]=x;
}
void update(int st,int dr,int val)
{
int st1=bucket(st);
int dr1=bucket(dr);
if(st1==dr1)
{
for(int j=st;j<=dr;j++)
{
F[st1][V[j]]--;
if(F[st1][V[j]]<=0)
F[st1].erase(V[i]);
V[j]+=val;
F[st1][V[j]]++;
}
return;
}
for(int j=st;j<bucket_start(st1+1);j++)
{
F[st1][V[j]]--;
if(F[st1][V[j]]<=0)
F[st1].erase(V[j]);
V[j]+=val;
F[st1][V[j]]++;
}
for(int j=st1+1;j<dr1;j++)
S[j]+=val;
for(int j=bucket_start(dr1);j<=dr;j++)
{
F[dr1][V[j]]--;
if(F[dr1][V[j]]<=0)
F[dr1].erase(V[j]);
V[j]+=val;
F[dr1][V[j]]++;
}
}
int query(int val)
{
for(int j=1;j<=nrb;j++)
if(F[j].find(val-S[j])!=F[j].end())
{
for(int l=bucket_start(j);l<bucket_start(j+1);l++)
if(V[l]+S[j]==val)
return I[l];
}
return -1;
}
int main()
{
fin>>n>>m;
for(i=1;i<n;i++)
{
fin>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
dfs(1,0);
rad=sqrt(k);
nrb=k/rad+(k%rad!=0);
for(i=1;i<=k;i++)
F[bucket(i)][0]++;
for(i=1;i<=m;i++)
{
fin>>T;
if(T==1)
{
fin>>p>>s;
update(first[p],last[p],s);
}
else
{
fin>>s;
fout<<query(s)<<"\n";
}
}
return 0;
}