Cod sursa(job #2398843)

Utilizator ianiIani Biro iani Data 6 aprilie 2019 11:44:37
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("arbore.in");
ofstream fout ("arbore.out");

const int NMAX=100005;

struct nod
{
    int v;
    nod *next;
}*a[NMAX];

int n,seq_len,seq[NMAX*2],firstpos[NMAX],lastpos[NMAX],value[NMAX];
bool ap[NMAX];

void dfs(int x)
{
    seq_len++;
    ap[x]=true;
    seq[seq_len] = x;
    firstpos[x] = seq_len;

    for (nod* j=a[x]; j; j=j->next)
        if (!ap[j->v])
            dfs(j->v);

    seq_len++;
    seq[seq_len] = -x;
    lastpos[x] = seq_len;
}

int main()
{
    int m;
    fin>>n>>m;
    for (int i=0; i<n-1; i++)
    {
        int x,y;
        fin>>x>>y;
        nod *nou=new nod;
        nou->v=y;
        nou->next=a[x];
        a[x]=nou;
        nou=new nod;
        nou->v=x;
        nou->next=a[y];
        a[y]=nou;
    }
    dfs(1);
    for (int i=0; i<m; i++)
    {
        char c;
        fin>>c;
        switch(c)
        {
        case '1':
        {
            int p,s;
            fin>>p>>s;
            for (int i=firstpos[p]; i<=lastpos[p]; i++)
                if (seq[i]>0)
                    value[seq[i]]+=s;
            break;
        }
        case '2':
        {
            int s;
            fin>>s;
            for (int i=1; i<=n; i++)
                if (value[i]==s)
                {
                    fout<<i<<'\n';
                    break;
                }
            break;
        }
        }
    }
    /*for (int i=1; i<=seq_len; i++)
        cout<<seq[i]<<' ';
    cout<<'\n';
    for (int i=1; i<=seq_len; i++)
        cout<<seq[i]<<' ';*/
    return 0;
}