Pagini recente » Cod sursa (job #2622742) | Cod sursa (job #771042) | Cod sursa (job #1040401) | Cod sursa (job #1519309) | Cod sursa (job #1794477)
#include <iostream>
#include<cstdio>
#include <vector>
using namespace std;
#define nmax 100100
#define DIM 10000
char buff[DIM];
int poz1=0;
void citeste(int &numar)
{
numar = 0;
//cat timp caracterul din buffer nu e cifra ignor
while (buff[poz1] < '0' || buff[poz1] > '9')
//daca am "golit" bufferul atunci il umplu
if (++poz1 == DIM)
fread(buff,1,DIM,stdin),poz1=0;
//cat timp dau de o cifra recalculez numarul
while ('0'<=buff[poz1] && buff[poz1]<='9')
{
numar = numar*10 + buff[poz1] - '0';
if (++poz1 == DIM)
fread(buff,1,DIM,stdin),poz1=0;
}
}
vector <int> v[nmax];
vector <int> g[nmax];
int last[nmax];
int arbore[nmax];
int poz[nmax];
int viz[nmax];
int d[nmax];
int s,ans,rad,n,m,i,a,b,q,x,z,k,curr;
void df(int x)
{
arbore[++k]=x;
poz[x]=k;
for(int i=0; i<v[x].size(); ++i)
df(v[x][i]);
last[poz[x]]=k;
}
void create(int x)
{
viz[x]=1;
for(int i=0; i<g[x].size(); ++i)
if(!viz[g[x][i]])
{
viz[g[x][i]]=1;
v[x].push_back(g[x][i]);
create(g[x][i]);
}
}
int main()
{
freopen("arbore.in","r",stdin);
freopen("arbore.out","w",stdout);
citeste(n);
citeste(q);
for(i=1; i<n; ++i)
{
citeste(a);
citeste(b);
g[a].push_back(b);
g[b].push_back(a);
}
k=0;
create(1);
df(1);
while(q--)
{
citeste(x);
switch(x)
{
case 1:
citeste(z);
citeste(s);
d[poz[z]]+=s;
d[last[poz[z]]+1]-=s;
break;
case 2:
citeste(s);
curr=0;
ans=-1;
for(i=1; i<=n; ++i)
{
curr+=d[i];
if(curr==s)
{
ans=arbore[i];
break;
}
}
cout<<ans<<'\n';
break;
}
}
}