Cod sursa(job #2789027)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 26 octombrie 2021 20:00:21
Problema Zvon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 1e5;
vector<int> g[1 + kN];
int dp[1 + kN];

void max_self(int &x, const int &y) {
  if (x < y) {
    x = y;
  }
}

void dfs(int u, int par) {
  g[u].erase(find(g[u].begin(), g[u].end(), par));
  for (int v : g[u]) {
    dfs(v, u);
  }
  sort(g[u].begin(), g[u].end(), [&](int x, int y) {
    return dp[x] > dp[y];
  });
  int wait = 1;
  for (int v : g[u]) {
    max_self(dp[u], dp[v] + wait++);
  }
}

void TestCase() {
  int n;
  fin >> n;
  for (int i = 1; i <= n; ++i) {
    g[i].clear();
    dp[i] = 0;
  }
  for (int i = 1; i < n; ++i) {
    int u, v;
    fin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  g[1].emplace_back(0);
  dfs(1, 0);
  fout << dp[1] << '\n';
}

int main() {
  int tests;
  fin >> tests;
  for (int tc = 1; tc <= tests; ++tc) {
    TestCase();
  }
  fin.close();
  fout.close();
  return 0;
}