Cod sursa(job #1787881)

Utilizator contrealMos Craciun contreal Data 25 octombrie 2016 10:39:38
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define nmax 100100

vector <int> v[nmax];
int mars[nmax];
int d[nmax];
int rel[nmax];
int r[nmax];
int s,ans;
int viz[nmax];
int rad,n,m,i,a,b,q,x,z;

void df(int x,int sum)
{
    d[x]+=rel[x]+sum;
    sum+=rel[x];
    rel[x]=0;
    if(d[x]==s)
        ans=x;
    for(int i=0; i<v[x].size(); ++i)
        if(!viz[v[x][i]])
        {
            viz[v[x][i]]=1;
            df(v[x][i],sum);
        }
}

int main()
{
    fin>>n>>q;
    for(i=1; i<n; ++i)
    {
        fin>>a>>b;
        v[a].push_back(b);
        r[b]=1;
    }
    for(i=1; i<=n; ++i)
        if(r[i]==0)
        {
            rad=i;
            break;
        }
    while(q--)
    {
        fin>>x;
        switch(x)
        {
        case 1:
            fin>>z>>s;
            rel[z]+=s;
            break;
        case 2:
            fin>>s;
            ans=-1;
            df(rad,0);
            for(i=1; i<=n; ++i)
                viz[i]=0;
            fout<<ans<<'\n';
            break;
        }
    }

}