Cod sursa(job #2186597)

Utilizator papinub2Papa Valentin papinub2 Data 25 martie 2018 19:36:21
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int Nmax = 100005;

vector<int> A[Nmax];

void DFS (int nod, vector<int>&Father)
{
    for (auto i = 0; i < A[nod].size(); i++)
    {
        int nod_curent = A[nod][i];

        if (Father[nod] == nod_curent) continue;

        Father[nod_curent] = nod;
        DFS(nod_curent, Father);
    }
}

void parcurgere (int nod, int suma, int&rez, bool OK, vector<int> val, vector<int> bani, vector<int> Father)
{
    if (OK == false)
    for (auto i = 0; i < A[nod].size(); i++)
    {
        int nod_curent = A[nod][i];

        if (Father[nod] == nod_curent) continue;

        bani[nod_curent] = val[nod_curent] + bani[nod];
        if (bani[nod_curent] == suma)
            rez = nod_curent, OK = true;

        parcurgere(nod_curent, suma, rez, OK, val, bani, Father);
    }
}

int main()
{
    int n, m;
    in >> n >> m;

    vector<int> val(n + 1), bani(n + 1), Father(n + 1);

    for (int i = 1; i < n; i++)
    {
        int x, y;
        in >> x >> y;

        A[x].push_back(y);
        A[y].push_back(x);
    }

    DFS(1, Father);

    for (int i = 1; i <= m; i++)
    {
        int tip, p, s;
        in >> tip;

        if (tip == 1)
        {
            in >> p >> s;
            val[p] = val[p] + s;
        }

        else

        {
            in >> s;
            int rez;
            bool OK = false;
            bani[1] = val[1];
            if (bani[1] == s)
                out << 1 << '\n';
            else
            {
                parcurgere(1, s, rez, OK, val, bani, Father);
                out << rez << '\n';
            }
        }
    }

    return 0;
}