Pagini recente » Monitorul de evaluare | Atasamentele paginii Clasament acm_practice | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3306655)
#include <fstream>
#include <vector>
#include <cassert>
#include <set>
using namespace std;
const int N=1e5+5,sqrt=100;
ifstream cin("arbore.in");
ofstream cout("arbore.out");
struct apar
{
int suma;
multiset<int>st;
int in,fin;
void init()
{
for(int i=in; i<=fin; i++)
st.insert(0);
}
} block[N];
vector<int>adj[N];
int euler[N],unde[N],sub[N],q,n,global;
void citeste()
{
cin>>n>>q;
for(int i=1; i<n; i++)
{
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
}
void dfs(int nod,int p)
{
global++;
euler[global]=nod;
unde[nod]=global;
sub[nod]=1;
for(auto u:adj[nod])
{
if(u!=p)
{
dfs(u,nod);
sub[nod]+=sub[u];
}
}
}
int ce[N];
int valori[N];
void update(int l,int r,int suma)
{
while(l<=r)
{
int parte=ce[l];
if(l==block[parte].in&&block[parte].fin<=r)
{
block[parte].suma+=suma;
l=block[parte].fin+1;
}
else
{
for(int i=l; i<=min(r,block[parte].fin); i++)
{
block[parte].st.erase(block[parte].st.find(valori[i]));
valori[i]+=suma;
block[parte].st.insert(valori[i]);
}
l=block[parte].fin+1;
}
}
}
int main()
{
citeste();
dfs(1,0);
for(int i=1; i<=n; i++)
{
int blk=(i-1)/sqrt;
ce[i]=blk;
if(i/sqrt!=blk)
block[blk].fin=i;
if(i==1||(i-2)/sqrt!=blk)
block[blk].in=i;
}
block[ce[n]].fin=n;
for(int i=0; i<=ce[n]; i++)
block[i].init();
for(int ind=1; ind<=q; ind++)
{
int tip;
cin>>tip;
if(tip==1)
{
int nod,suma;
cin>>nod>>suma;
int l=unde[nod];
int r=unde[nod]+sub[nod]-1;
update(l,r,suma);
}
else
{
int val;
cin>>val;
int ans=-1;
for(int i=0; i<=ce[n]; i++)
{
int offset=block[i].suma;
if(block[i].st.find(val-offset)!=block[i].st.end())
{
for(int j=block[i].in; j<=block[i].fin; j++)
{
if(valori[j]==(val-offset))
{
ans=euler[j];
break;
}
}
break;
}
}
cout<<ans<<'\n';
}
}
return 0;
}