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