Cod sursa(job #2517388)

Utilizator rapunzelMihnea Andreescu rapunzel Data 3 ianuarie 2020 14:44:51
Problema Revolta Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 2.2 kb
/// orz tourist
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

__attribute__((always_inline)) void read(int &num) {
  static char inBuffer[0x30D40];
  static unsigned int p = 0x30D3F; num = 0x0;
  while(inBuffer[p] < 0x30 | inBuffer[p] > 0x39) {
    ++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
  }
  while(inBuffer[p] > 0x2F & inBuffer[p] < 0x3A) {
    num = num * 0xA + inBuffer[p] - 0x30;
    ++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
  }
}

const int N = 100000;
int n, p[N], up[N], down[N], md[N], aux_up[N];
vector<int> g[N];

void dfs1(int a) {
  int m1 = 0, m2 = 0;
  md[a] = 1;
  for (auto &b : g[a]) {
    if (b != p[a]) {
      p[b] = a;
      dfs1(b);
      md[a] = max(md[a], 1 + md[b]);
      if (md[b] > m1) {
        m2 = m1;
        m1 = md[b];
      } else {
        if (md[b] > m2) {
          m2 = md[b];
        }
      }
    }
  }
  down[a] = m1 + m2 + 1;
}

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

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

  aux_up[0] = 1;
  p[0] = -1;
  int t;
  read(t);
  for (int tc = 0; tc < t; tc++) {
    read(n);
    for (int i = 0; i < n; i++) {
      g[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
      int a, b;
      read(a);
      read(b);
      g[a].push_back(b);
      g[b].push_back(a);
    }
    dfs1(0);
      continue;
    dfs2(0);
    int sol = (1 << 30);
    for (int i = 0; i < n; i++) {
      int d1 = up[i];
      int d2 = down[i];
      int cur = max(d1 / 2 + d2 / 2 + 2, max(d1, d2)) - 1;
      sol = min(sol, cur);
    }
    printf("%d\n", sol);
  }
}