Cod sursa(job #1794463)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 1 noiembrie 2016 12:22:19
Problema Arbore Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream f("arbore.in");
ofstream g("arbore.out");
vector<int>v[100001],w[100001];
int n,m,i,j,x,y,sum,p,t,S[100001],d[100001],ans;
bool viz[100001];
int DFS(int nod,int s)
{
    viz[nod]=1;
    s+=S[nod];
    if(s==sum)
        {
            ans=nod;
            return 1;
        }
    for(int i=0;i<v[nod].size();i++)
        if(!viz[v[nod][i]])
        {
            DFS(v[nod][i],s);
        }
}
void create(int nod)
{
    viz[nod]=1;
    for(int i=0;i<w[nod].size();i++)
        if(!viz[w[nod][i]])
    {
        v[nod].push_back(w[nod][i]);
        create(w[nod][i]);
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<n;i++)
    {
        f>>x>>y;
        w[x].push_back(y);
        w[y].push_back(x);
    }
    create(1);
    for(i=1;i<=m;i++)
    {
        f>>t;
        if(t==1)
        {
            f>>p>>sum;
            S[p]+=sum;
        }
        else
        {
            f>>sum;
            for(j=1;j<=n;j++)
                viz[j]=0;
            ans=-1;
            DFS(1,0);
            g<<ans<<'\n';
        }
    }
}