Pagini recente » Cod sursa (job #957549) | Statistici Fodor Rares-Costin (FRD233) | Simulare OJI - HLO, Liceu Avansati | Monitorul de evaluare | Cod sursa (job #1710398)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("revolta.in");
ofstream fout("revolta.out");
const int MAXN = 100100;
int dad[MAXN], bestLant[MAXN], bestLant2[MAXN], diaCur[MAXN], bestDia[MAXN], bestDia2[MAXN], bestLantSus[MAXN];
int fbl[MAXN], fbl2[MAXN], fd[MAXN], fd2[MAXN], n, computedDiametru[MAXN];
vector<int> graph[MAXN];
int bestRez = 3 * MAXN;
void explorare(int nod) {
for (auto it: graph[nod]) {
if (it == dad[nod]) continue;
if (!dad[it]) {
dad[it] = nod;
explorare(it);
}
}
}
void get_lanturi(int nod) {
for (auto it: graph[nod]) {
if (it == dad[nod]) continue;
get_lanturi(it);
if (bestLant[it] + 1 > bestLant[nod]) {
bestLant2[nod] = bestLant[nod];
fbl2[nod] = fbl[nod];
bestLant[nod] = bestLant[it] + 1;
fbl[nod] = it;
}
else if (bestLant[it] + 1 > bestLant2[nod]) {
bestLant2[nod] = bestLant[it] + 1;
fbl2[nod] = it;
}
}
diaCur[nod] = bestLant[nod] + bestLant2[nod];
}
void get_diametre(int nod) {
for (auto it: graph[nod]) {
if (it == dad[nod]) continue;
get_diametre(it);
if (diaCur[it] > diaCur[nod])
diaCur[nod] = diaCur[it];
if (diaCur[it] > bestDia[nod]) {
bestDia2[nod] = bestDia[nod];
fd2[nod] = fd[nod];
bestDia[nod] = diaCur[it];
fd[nod] = it;
}
else if (diaCur[it] > bestDia2[nod]) {
bestDia2[nod] = diaCur[it];
fd2[nod] = it;
}
}
}
void get_lant_sus(int nod) {
int b1, b2;
b1 = bestLantSus[dad[nod]] + 1;
if (fbl[dad[nod]] == nod)
b2 = bestLant2[dad[nod]] + 1;
else
b2 = bestLant[dad[nod]] + 1;
if (dad[nod] != 0)
bestLantSus[nod] = max(b1, b2);
for (auto it: graph[nod]) {
if (nod != dad[it]) continue;
get_lant_sus(it);
}
}
void solve(int nod) {
for (auto it : graph[nod]) {
if (it == dad[nod]) continue;
int d1 = diaCur[it];
int d2 = 0;
if (it == fd[nod])
d2 = bestDia2[nod];
else
d2 = bestDia[nod];
int l2 = 0;
if (it == fbl[nod])
l2 = bestLant2[nod];
else
l2 = bestLant[nod];
int d2bl = 0;
d2bl = l2 + bestLantSus[nod];
int d2bd = 0;
d2bd = computedDiametru[dad[nod]];
int diametru2 = max(d2, max(d2bl, d2bd));
computedDiametru[it] = diametru2;
int rez;
rez = max(d1, diametru2);
int newD = d1 / 2 + diametru2 / 2 + 1;
if (d1 % 2 == 1)
++newD;
if (diametru2 % 2 == 1)
++newD;
rez = max (newD, rez);
if (rez < bestRez)
bestRez = rez;
solve(it);
}
}
int main() {
int t;
fin >> t;
for (; t; --t) {
fin >> n;
for (int i = 0; i <= n; ++i) {
graph[i].clear();
bestLant[i] = 0;
bestLant2[i] = 0;
bestDia[i] = 0;
bestDia2[i] = 0;
diaCur[i] = 0;
bestLantSus[i] = 0;
dad[i] = 0;
computedDiametru[i] = 0;
}
bestRez = 3 * MAXN;
for (int i = 1; i < n; ++i) {
int x, y;
fin >> x >> y;
++x; ++y;
graph[x].push_back(y);
graph[y].push_back(x);
}
explorare(1);
get_lanturi(1);
get_diametre(1);
get_lant_sus(1);
solve(1);
fout << bestRez << "\n";
}
return 0;
}