Pagini recente » Rating Alex Cristian (bishopp) | Cod sursa (job #264207) | Rating UPB Vasile Raul Tache Razvan Murgoci Gabriela (UPB_Vasile_Tache_Murgoci) | Cod sursa (job #1056281) | Cod sursa (job #2517386)
/// 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);
}
continue;
dfs1(0);
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);
}
}