Cod sursa(job #2517368)

Utilizator rapunzelMihnea Andreescu rapunzel Data 3 ianuarie 2020 14:05:48
Problema Revolta Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 2.6 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cctype>

using namespace std;

const int SIZE = 1 << 17;
int pointer = SIZE;
char buffer[SIZE];

char Advance() {
    if (pointer == SIZE) {
        fread(buffer, 1, SIZE, stdin);
        pointer = 0;
    }
    return buffer[pointer++];
}

int Read() {
    int answer = 0;
    char ch = Advance();
    while (!isdigit(ch))
        ch = Advance();
    while (isdigit(ch)) {
        answer = answer * 10 + ch - '0';
        ch = Advance();
    }
    return answer;
}

const int N = (int) 1e5 + 7;
int n;
vector<int> g[N];
bool vis[N];
int max_dep[N];
int under[N];
int up[N];
int aux_up[N];
int level[N];
int par[N];

void build_down(int a) { /// begin
  vis[a] = 1;
  vector<int> kids;
  for (auto &b : g[a]) if (vis[b] == 0) kids.push_back(b), build_down(b); else par[a] = b;
  g[a] = kids;
  if (g[a].empty()) {max_dep[a] = 1; return;}
  for (auto &b : g[a]) {
    max_dep[a] = max(max_dep[a], 1 + max_dep[b]);
    under[a] = max(under[a], under[b]);
  }
  kids = {0, 0};
  int m1 = 0, m2 = 0;
  /// m1 > m2
  for (auto &b : g[a]) {///kids.push_back(max_dep[b]);
    if (max_dep[b] > m1) {
      m2 = m1;
      m1 = max_dep[b];
    } else if (max_dep[b] > m2) m2 = max_dep[b];
  }
  under[a] = max(under[a], m1 + m2 + 1);
}

void build_up(int a) { /// finish
  int p = par[a];
  if (p != -1) {
    aux_up[a] = aux_up[p] + 1;
    for (auto &b : g[p]) if (a != b) aux_up[a] = max(aux_up[a], 2 + max_dep[b]);
    up[a] = max(up[a], up[p]);
    int m1 = 0, m2 = 0;
    for (auto &b : g[p]) if (b != a) {
      if (max_dep[b] > m1) {
        m2 = m1;
        m1 = max_dep[b];
      } else if (max_dep[b] > m2) m2 = max_dep[b];
    }
    up[a] = max(up[a], m1 + m2 + 1);
  } else {
    aux_up[a] = 1;
  }

  up[a] = max(up[a], aux_up[a]);
  for (auto &b : g[a]) {level[b] = 1 + level[a], build_up(b);}
}

int main() {
  freopen ("revolta.in", "r", stdin);
  freopen ("revolta.out", "w", stdout);

  int t, a, b; t = Read();
  for (int tc = 0; tc < t; tc++) {
    n = Read();
    for (int i = 0; i < n; i++) g[i].clear(), vis[i] = 0, max_dep[i] = 0, under[i] = 0, up[i] = 0, aux_up[i] = 0, level[i] = 0, par[i] = -1;
    for (int i = 0; i < n - 1; i++) {
      int a, b; a = Read(); b = Read();
      g[a].push_back(b);
      g[b].push_back(a);
    }
    level[0] = 1;
    build_down(0);
    build_up(0);
    int sol = (1 << 30);
    for (int i = 0; i < n; i++) for (auto &j : g[i]) sol = min(sol, max(max(up[i], under[j]), up[i] / 2 + under[j] / 2 + 2));
    sol--;
    printf("%d\n", sol);
  }
}