Pagini recente » Monitorul de evaluare | Cod sursa (job #1186044) | Istoria paginii problema/album | Cod sursa (job #1384225) | Cod sursa (job #1710330)
#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[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[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[x] = max(max_diameter[x], max_diameter[it]);
}
}
max_diameter[x] = max(max_diameter[x], down[0][x].fi + down[1][x].fi);
ans = max(ans, max_diameter[x]);
}
void dfs_up(int x, int f) {
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);
up[x] = max(up[x], up[f] + 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;
}
int diameter_up = max(wave[x], up[x] + best_down);
int diameter_down = max_diameter[it];
int diameter_cut = max(diameter_up, diameter_down);
diameter_cut = max(diameter_cut, (diameter_up + 1) / 2 + (diameter_down + 1) / 2 + 1);
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;
}