Cod sursa(job #915135)

Utilizator lily3Moldovan Liliana lily3 Data 14 martie 2013 19:15:10
Problema Arbore Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ofstream g("arbore.out");

int i,j,n,m,x,y,tip,p,s,sum[1000001],s1[1000001],ok,nr=0;
int ic[100001],sf[100001];
bool viz[1000001];
vector<int> a[100001];
void df(int x)
{
    int i;
    viz[x]=1;
    ++nr;
    ic[x]=sf[x]=nr;
    for(i=0;i<a[x].size();++i)
    if(!viz[a[x][i]])
    {
        df(a[x][i]);
        sf[x]=nr;
    }
}
int main()
{
    ifstream f("arbore.in");

    f>>n>>m;
    for(i=1;i<n;++i)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    df(1);
    for(i=1;i<=m;++i)
    {
        f>>tip;
        if(tip==1)
        {
            f>>p>>s;
            sum[ic[p]]+=s;
            sum[sf[p]+1]-=s;
        }
        else
        {
            f>>s;
            for(j=1;j<=n;++j)
            s1[j]=s1[j-1]+sum[j];
            ok=0;
            for(j=1;j<=n&&!ok;++j)
            if(s1[ic[j]]==s)
            g<<j<<"\n",ok=1;
            if(!ok)
                g<<"-1"<<"\n";
        }
    }
    return 0;
}