Cod sursa(job #1787989)

Utilizator CrystyAngelDinu Cristian CrystyAngel Data 25 octombrie 2016 13:41:52
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 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];
vector <int> g[nmax];
int arbore[nmax];
int last[nmax];
int poz[nmax];
int viz[nmax];
int d[nmax];
int s,ans,rad,n,m,i,a,b,q,x,z,k,curr;

void df(int x)
{
    arbore[++k]=x;
    poz[x]=k;
    for(int i=0; i<v[x].size(); ++i)
        df(v[x][i]);
    last[poz[x]]=k;
}

void create(int x)
{
    viz[x]=1;
    for(int i=0; i<g[x].size(); ++i)
        if(!viz[g[x][i]])
        {
            viz[g[x][i]]=1;
            v[x].push_back(g[x][i]);
            create(g[x][i]);
        }
}

int main()
{
    fin>>n>>q;
    for(i=1; i<n; ++i)
    {
        fin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    k=0;
    create(1);
    df(1);

    while(q--)
    {
        fin>>x;
        switch(x)
        {
        case 1:
            fin>>z>>s;
            d[poz[z]]+=s;
            d[last[poz[z]]+1]-=s;
            break;
        case 2:
            fin>>s;
            curr=0;
            ans=-1;
            for(i=1; i<=n; ++i)
            {
                curr+=d[i];
                if(curr==s)
                {
                    ans=i;
                    break;
                }
            }
            fout<<ans<<'\n';
            break;
        }
    }
}