Pagini recente » Cod sursa (job #2959838) | Cod sursa (job #3252821) | Cod sursa (job #373245) | Cod sursa (job #1386709) | Cod sursa (job #1709513)
#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
const int N = 100100;
int n, d[N], lant[N], rmin;
vector<int> v[N];
multiset<int> h[N];
void init() {
int i;
for(i = 0; i <= n; ++i) {
v[i].clear();
h[i].clear();
d[i] = 0;
lant[i] = 0;
}
}
void df(int nod, int p) {
int l1 = 0, l2 = 0;
for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) if(*it != p) {
df(*it, nod);
lant[nod] = max(lant[nod], lant[*it] + 1);
d[nod] = max(d[nod], d[*it]);
int e = lant[*it] + 1;
if(e > l1) {
l2 = l1;
l1 = e;
}
else if(e > l2)
l2 = e;
}
d[nod] = max(d[nod], l1 + l2);
}
void df2(int nod, int p, int dup, int lup) {
int l1 = lup + 1, l2 = 0;
h[nod].insert(lup);
for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) if(*it != p) {
int e = lant[*it] + 1;
h[nod].insert(e);
if(h[nod].size() > 3)
h[nod].erase(h[nod].begin());
++e;
if(e > l1) {
l2 = l1;
l1 = e;
}
else if(e > l2)
l2 = e;
}
int vv = 0;
for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it) if(*it != p) {
vv = 1;
int nlup = l1, ndup = 0;
if(l1 == lant[*it] + 2)
nlup = l2;
ndup = nlup - 1;
if(h[nod].size() > 2) {
bool flag = 0;
multiset<int>::iterator jt = h[nod].find(lant[*it] + 1);
if(jt != h[nod].end()) {
flag = true;
h[nod].erase(jt);
}
jt = h[nod].end();
jt--;
int sc = *jt;
--jt;
sc += *jt;
ndup = max(ndup, sc);
if(flag)
h[nod].insert(lant[*it] + 1);
}
int solc = (ndup + 1) / 2 + (d[*it] + 1) / 2 + 1;
int rc = max(ndup, max(d[*it], solc));
rmin = min(rmin, rc);
ndup = nlup;
df2(*it, nod, ndup, nlup);
}
//cout << nod << " " << dup << " " << lup << " " << rmin << "\n";
if(vv == 0) {
rmin = min(rmin, max(dup, lup));
}
}
void sol() {
int i, j;
cin >> n;
init();
for(i = 1; i < n; ++i) {
int a, b;
scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
df(0, -1);
rmin = 1000000;
df2(0, -1, 0, 0);
cout << min(d[0], rmin) << "\n";
}
int main()
{int i, j;
freopen("revolta.in", "r", stdin);
freopen("revolta.out", "w", stdout);
int t;
cin >> t;
while(t--)sol();
return 0;
}