Pagini recente » Cod sursa (job #1797725) | Monitorul de evaluare | Diferente pentru preoni-2007/runda-1 intre reviziile 17 si 18 | Cod sursa (job #123553) | Cod sursa (job #1710353)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
const int NMAX = 100005;
int n, ans;
int up[NMAX];
int wave[NMAX];
int max_diameter_down[NMAX];
int max_diameter_up[NMAX];
pii down[3][NMAX];
vector<int> v[NMAX];
void reset() {
ans = 0;
for (int i = 1; i <= n; i++) {
v[i].clear();
up[i] = 0;
wave[i] = 0;
max_diameter_down[i] = 0;
for (int j = 0; j < 3; j++)
down[j][i] = {0, 0};
}
}
void dfs_down(int x, int f) {
for (auto it : v[x]) {
if (it != f) {
dfs_down(it, x);
int new_chain = 1 + down[0][it].fi;
for (int j = 0; j < 3; j++) {
if (new_chain > down[j][x].fi) {
for (int k = 2; k > j; k--) {
down[k][x] = down[k - 1][x];
}
down[j][x] = {new_chain, it};
break;
}
}
max_diameter_down[x] = max(max_diameter_down[x], max_diameter_down[it]);
}
}
max_diameter_down[x] = max(max_diameter_down[x], down[0][x].fi + down[1][x].fi);
ans = max(ans, max_diameter_down[x]);
}
void dfs_up(int x, int f) {
pii best0 = {0, 0}, best1 = {0, 0};
for (auto it : v[x]) {
if (it != f) {
if (max_diameter_down[it] > best0.fi) {
best1 = best0;
best0 = {max_diameter_down[it], it};
} else if (max_diameter_down[it] > best1.fi) {
best1 = {max_diameter_down[it], it};
}
}
}
for (auto it : v[x]) {
if (it != f) {
if (f) {
int best_down;
if (down[0][f].se == x) {
best_down = down[1][f].fi;
} else {
best_down = down[0][f].fi;
}
up[x] = max(1 + up[f], 1 + best_down);
} else {
up[x] = 0;
}
int best_wave;
if (down[0][x].se == it) {
best_wave = down[1][x].fi + down[2][x].fi;
} else if (down[1][x].se == it) {
best_wave = down[0][x].fi + down[2][x].fi;
} else {
best_wave = down[0][x].fi + down[1][x].fi;
}
wave[x] = max(wave[f], best_wave);
int best_down;
if (down[0][x].se == it) {
best_down = down[1][x].fi;
} else {
best_down = down[0][x].fi;
}
max_diameter_up[x] = max(max_diameter_up[f], up[x] + best_down);
if (best0.se == it) {
max_diameter_up[x] = max(max_diameter_up[x], best1.fi);
} else {
max_diameter_up[x] = max(max_diameter_up[x], best0.fi);
}
int diameter_up = max(wave[x], max_diameter_up[x]);
int diameter_down = max_diameter_down[it];
int diameter_cut = max(diameter_up, diameter_down);
diameter_cut = max(diameter_cut, (diameter_up + 1) / 2 + (diameter_down + 1) / 2 + 1);
/* cerr << x << " " << it << " " << diameter_up << " " << diameter_down << endl; */
ans = min(ans, diameter_cut);
dfs_up(it, x);
}
}
}
int main() {
cin.sync_with_stdio(false);
freopen("revolta.in", "r", stdin);
freopen("revolta.out", "w", stdout);
int t;
cin >> t;
for (; t; t--) {
cin >> n;
reset();
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
x++;
y++;
v[x].pb(y);
v[y].pb(x);
}
dfs_down(1, 0);
dfs_up(1, 0);
cout << ans << '\n';
}
return 0;
}