Cod sursa(job #2517362)

Utilizator rapunzelMihnea Andreescu rapunzel Data 3 ianuarie 2020 13:58:15
Problema Revolta Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 2.12 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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(int a) {
  vis[a] = 1;
  vector<int> kids;
  for (auto &b : g[a]) if (vis[b] == 0) kids.push_back(b), build(b); else par[a] = b;
  g[a] = kids;
}

void build_max_dep(int a) {
  if (g[a].empty()) {max_dep[a] = 1; return;}
  for (auto &b : g[a]) {
    build_max_dep(b);
    max_dep[a] = max(max_dep[a], 1 + max_dep[b]);
  }
}

void build_under(int a) {
  for (auto &b : g[a]) build_under(b), under[a] = max(under[a], under[b]);
  vector<int> kids = {0, 0};
  for (auto &b : g[a]) kids.push_back(max_dep[b]);
  sort(kids.rbegin(), kids.rend());
  under[a] = max(under[a], kids[0] + kids[1] + 1);
}

void build_up(int a) {
  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]);
    vector<int> niet = {0, 0};
    for (auto &b : g[p]) if (b != a) niet.push_back(max_dep[b]);
    sort(niet.rbegin(), niet.rend());
    up[a] = max(up[a], niet[0] + niet[1] + 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; scanf("%d", &t);
  for (int tc = 0; tc < t; tc++) {
    scanf("%d", &n);
    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; scanf("%d %d", &a, &b);
      g[a].push_back(b);
      g[b].push_back(a);
    }
    build(0);
    build_max_dep(0);
    build_under(0);
    level[0] = 1;
    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);
  }
}