Cod sursa(job #2378978)

Utilizator hrazvanHarsan Razvan hrazvan Data 12 martie 2019 19:41:15
Problema Zvon Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAXN 100000
int ut[MAXN], nd[2 * MAXN], nxt[2 * MAXN], dr;

inline void add(int x, int y){
  nd[dr] = y;
  nxt[dr] = ut[x];
  ut[x] = dr;
  dr++;
}

int calc(int x, int t){
  int p = ut[x];
  std::vector<int> v;
  while(p != -1){
    if(nd[p] != t)
      v.push_back(calc(nd[p], x));
    p = nxt[p];
  }
  std::sort(v.begin(), v.end());
  int i, mx = 0, n;
  n = v.size();
  for(i = 1; i <= n; i++){
    if(mx < v[n - i] + i)
      mx = v[n - i] + i;
  }
  return mx;
}

int main(){
  freopen("zvon.in", "r", stdin);
  freopen("zvon.out", "w", stdout);
  int t, n, i, x, y;
  scanf("%d", &t);
  for(; t > 0; t--){
    scanf("%d", &n);
    memset(ut, -1, sizeof ut);
    dr = 0;
    for(i = 1; i < n; i++){
      scanf("%d%d", &x, &y);
      x--;  y--;
      add(x, y);
      add(y, x);
    }
    printf("%d\n", calc(0, -1));
  }
  return 0;
}