Cod sursa(job #915030)

Utilizator lily3Moldovan Liliana lily3 Data 14 martie 2013 17:51:30
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

int i,j,n,m,x,y,tip,p,s,sum[100001],s1[1000001],cr[1000001],start;
int tata[1000001],niv[1000001];
bool viz[1000001];
vector<int> a[100001];
void init()
{
    for(int i=1;i<=n;++i)
        viz[i]=0;
}
void df(int x)
{
    int i;
    viz[x]=1;
    for(i=0;i<a[x].size();++i)
    if(!viz[a[x][i]])
    {
        niv[a[x][i]]=niv[x]+1;
        tata[a[x][i]]=x;
        df(a[x][i]);
    }
}
void det(int x)
{
    int i;
    viz[x]=1;
    for(i=0;i<a[x].size();++i)
        if(!viz[a[x][i]]&&niv[a[x][i]]>niv[x])
        {
            sum[a[x][i]]+=sum[x];
            det(a[x][i]);
        }
        s1[sum[x]]=x;
}
int main()
{
    ifstream f("arbore.in");
    ofstream g("arbore.out");
    f>>n>>m;
    for(i=1;i<n;++i)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    df(1);
    start=0;
    niv[0]=10000000;
    for(i=1;i<=m;++i)
    {
        f>>tip;

        if(tip==1)
        {
            f>>p>>s;
            if(niv[p]<niv[start])
            start=p;
            else
            if(niv[p]==niv[start])
            start=tata[p];
            sum[p]+=s;
        }
        else
        {
            init();
            f>>s;
            det(start);
            if(s1[s])
            g<<s1[s]<<"\n";
            else
                g<<"-1"<<"\n";
        }
    }
    return 0;
}