Pagini recente » Cod sursa (job #3137337) | Cod sursa (job #2374566) | Cod sursa (job #2293544) | Cod sursa (job #2810841) | Cod sursa (job #1710008)
#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;
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 update_diametre (int nod) {
for (auto it : graph[nod]) {
if (it == dad[nod]) continue;
update_diametre(it);
if (bestDia[nod] > diaCur[nod])
diaCur[nod] = bestDia[nod];
}
}
void get_diametre(int nod) { //vezi frunze
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;
bestLantSus[nod] = max(b1, b2);
}
void solve(int nod) {
for (auto it : graph[nod]) {
if (it == dad[nod]) continue;
solve(it);
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;
if (nod == fd[dad[nod]])
d2bd = bestDia2[dad[nod]];
else
d2bd = bestDia[dad[nod]];
int diametru2 = max(d2, max(d2bl, d2bd));
int rez;
rez = max(d1, diametru2);
int newD = d1 / 2 + diametru2 / 2 + 1;
rez = max (newD, rez);
if (rez < bestRez);
bestRez = rez;
}
}
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;
}
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);
update_diametre(1);
solve(1);
fout << bestRez << "\n";
}
return 0;
}