Cod sursa(job #332414)

Utilizator DraStiKDragos Oprica DraStiK Data 17 iulie 2009 18:38:14
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#define DIM 100005
struct nod {int x;
            nod *urm;} *lst[DIM];
int s[DIM];
int n,m;

void add (int a,int b)
{
    nod *p=new nod;
    p->x=b;
    p->urm=lst[a];
    lst[a]=p;
}

void read ()
{
    int i,x,y;
    scanf ("%d%d",&n,&m);
    for (i=1; i<n; ++i)
    {
        scanf ("%d%d",&x,&y);
        add (x,y);
    }
}

void update (int start,int sum)
{
    nod *p;
    s[start]+=sum;
    for (p=lst[start]; p; p=p->urm)
        update (p->x,sum);
}

int query (int sum)
{
    int i;
    for (i=1; i<=n; ++i)
        if (s[i]==sum)
            return i;
    return -1;
}

void solve ()
{
    int i,x,y,cod;
    for (i=1; i<=m; ++i)
    {
        scanf ("%d",&cod);
        if (cod==1)
        {
            scanf ("%d%d",&x,&y);
            update (x,y);
        }
        else if (cod==2)
        {
            scanf ("%d",&x);
            printf ("%d",query (x));
            if (i!=m)
                printf ("\n");
        }
    }
}

int main ()
{
    freopen ("arbore.in","r",stdin);
    freopen ("arbore.out","w",stdout);
    read ();
    solve ();
    return 0;
}