Cod sursa(job #2926743)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 18 octombrie 2022 16:47:06
Problema Arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

///#include <tryhardMODE>
///#include <GODMODE::ON>

using namespace std;

ifstream fin ("arbore.in");
ofstream fout ("arbore.out");

const int NMAX=1e5+5;

vector<int>v[NMAX];
int sume[NMAX];
bool viz[NMAX];
int dist;

int solve(int p,int val)
{
    int ind=-1;
    dist=max(dist,p);
    val=val-sume[p];
    viz[p]=1;
    if(val<0)
        return -1;
    else
    {
        if(val==0)
            return p;
        else
        {
            for(auto i:v[p])
            {
                if(viz[i]==0)
                    ind=max(ind,solve(i,val));
            }
            return ind;
        }
    }
}

int main()
{
    int n,m,t,i,j,x,y;
    fin>>n>>m;
    for(i=1;i<n;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    while(m--)
    {
        fin>>t;
        if(t==1)
        {
            fin>>x>>y;
            sume[x]=sume[x]+y;
        }
        else
        {
            fin>>x;
            dist=0;
            fout<<solve(1,x)<<"\n";
            for(i=1;i<=dist;i++)
                viz[i]=0;
        }
    }
    return 0;
}