Cod sursa(job #2912188)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 7 iulie 2022 11:35:15
Problema Arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <vector>

struct Nod {
  int s = 0;
  int parinte;
  std::vector<int> copii;
};

std::vector<Nod> noduri;

int DFS(int nod, int s) {
  int maxVal = -2;
  s = s - noduri[nod].s;
  if (s == 0)
    return nod;
  if (s < 0)
    return -2;
  for (int copil : noduri[nod].copii)
    maxVal = std::max(DFS(copil, s), maxVal);
  return maxVal;
}

int main() {
  FILE *fin, *fout;
  int n, m;
  int q, p, nod, s, i;

  fin = fopen("arbore.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  noduri.resize(n);

  for (i = 0; i < n - 1; i++) {
    fscanf(fin, "%d%d", &p, &nod);
    p--, nod--;
    noduri[p].copii.push_back(nod);
  }

  /*  printf("%d %d\n", n, m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < noduri[i].copii.size(); j++) {
      printf("%d ", noduri[i].copii.at(j));
    }
    putc('\n', stdout);
  } */

  fout = fopen("arbore.out", "w");

  for (i = 0; i < m; i++) {
    fscanf(fin, "%d", &q);
    if (q == 1) {
      fscanf(fin, "%d%d", &p, &s);
      p--; noduri[p].s += s;
    } else {
      fscanf(fin, "%d", &s);
      fprintf(fout, "%d\n", DFS(0, s) + 1);
    }
  }


  fclose(fin);

  fclose(fout);

  return 0;
}