Pagini recente » Cod sursa (job #764182) | Cod sursa (job #622674) | Cod sursa (job #1135795) | Cod sursa (job #1709251) | Cod sursa (job #930899)
Cod sursa(job #930899)
#include<stdio.h>
#include<vector>
using namespace std;
#define nmax 100006
long n, m, i, op, sac, a, b, ne, x, s, ii;
long sum[nmax], v[nmax], p1[nmax], p2[nmax];
vector <long> ma[nmax];
bool viz[nmax];
void citire()
{
scanf("%ld %ld",&n,&m);
for (i=1;i<=n-1;i++)
{
scanf("%ld %ld",&a,&b);
ma[a].push_back(b); ma[b].push_back(a);
}
}
void dfs(long nod)
{
v[++ne]=nod; p1[nod]=ne;
viz[nod]=1;
vector <long> ::iterator it;
for (it=ma[nod].begin();it!=ma[nod].end();it++)
if (!viz[*it])
dfs(*it);
p2[nod]=ne+1;
}
int main()
{
freopen("arbore.in","r",stdin);
freopen("arbore.out","w",stdout);
citire();
dfs(1);
for (i=1;i<=m;i++)
{
scanf("%ld",&op);
if (op==1)
{
scanf("%ld %ld",&x,&s);
sum[p1[x]]+=s; sum[p2[x]]-=s;
}
if (op==2)
{
scanf("%ld",&s);
sac=0; x=-1;
for (ii=1;ii<=n;ii++)
{
sac+=sum[ii];
if(sac==s)
{ x=v[ii]; break; }
}
printf("%ld\n",x);
}
}
return 0;
}