Cod sursa(job #2680013)

Utilizator stefantagaTaga Stefan stefantaga Data 2 decembrie 2020 12:18:26
Problema Arbore Scor 50
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("arbore.in");
ofstream g("arbore.out");
int nr[500005],arb[800005],q,n,m,x,y,i,viz[200005],rad,prim[200005],ult[200005],tip,sol;
vector <int> v[100005];
void dfs (int x)
{
    int i;
    viz[x]=1;
    nr[++q]=x;
    for (i=0;i<v[x].size();i++)
    {
        if (viz[v[x][i]]==0)
        {
            dfs(v[x][i]);
            nr[++q]=x;
        }
    }
}
int main()
{
    f>>n>>m;
    for (i=1;i<n;i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    for (i=1;i<=q;i++)
    {
        if (prim[nr[i]]==0)
        {
            prim[nr[i]]=i;
        }
        ult[nr[i]]=i;
    }
    for (int j=1;j<=m;j++)
    {
         f>>tip;
         if (tip==1)
         {
             f>>x>>y;
             arb[prim[x]]+=y;
             arb[ult[x]+1]-=y;
         }
         else
         {
             f>>y;
             sol=-1;
             int val=0;
             for (i=1;i<=q;i++)
             {
                 val+=arb[i];
                 if (val==y)
                 {
                     sol=nr[i];
                 }
             }
             g<<sol<<'\n';
         }
    }
    return 0;
}