Cod sursa(job #930893)

Utilizator lianaliana tucar liana Data 27 martie 2013 21:13:10
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#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 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);
    }
}

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(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;
}