Pagini recente » Cod sursa (job #639012) | Cod sursa (job #2819496) | Cod sursa (job #3264732) | Cod sursa (job #1186077) | Cod sursa (job #2517383)
/// orz tourist
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
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;
scanf("%d", &t);
for (int tc = 0; tc < t; tc++) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
g[i].clear();
}
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);
}
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);
}
}