Pagini recente » Cod sursa (job #1355) | Cod sursa (job #138871) | Cod sursa (job #1550419) | Rating UNIOVICT (yteam) | Cod sursa (job #2709012)
#include <fstream>
#include <vector>
#include <cstring>
#define pp std::cout<<"..............\n"
#define MAX(a, b) (((a)>(b))?(a):(b))
#define MIN(a, b) (((a)<(b))?(a):(b))
const int nmax = 1e5 + 5;
std::vector<int>l[nmax], diametru;
int h[nmax], tata[nmax], ap[nmax], mxd[nmax], mxl[nmax], mx[nmax][2];
void dfs1(int from, int dad = 0) {
h[from] = h[dad] + 1;
tata[from] = dad;
for(int to:l[from])
if(to!=dad)
dfs1(to, from);
}
void dfs2(int from, int dad = 0) {
int mx1, mx2;
mx1 = mx2 = 0;
for(int to:l[from])
if(to!=dad and !ap[to]){
dfs2(to, from);
mxd[from] = MAX(mxd[from], mxd[to]);
if(mxl[to] >= mx1) mx2 = mx1, mx1 = mxl[to] + 1;
else if(mxl[to] >= mx2) mx2 = mxl[to] + 1;
}
mxl[from] = mx1;
mxd[from] = MAX(mxd[from], mx1 + mx2);
}
std::ifstream fin("revolta.in");
std::ofstream fout("revolta.out");
void solve() {
int n, x, y;
fin>>n;
///Reset
for(int i=1;i<=n;i++) l[i].clear();
diametru.clear();
memset(ap, 0, sizeof(ap));
memset(mxl, 0, sizeof(mxl));
memset(mxd, 0, sizeof(mxd));
///Build graph
for(int i=1;i<n;i++) {
fin>>x>>y;
l[x+1].push_back(y+1);
l[y+1].push_back(x+1);
}
///Find diameter
h[0] = -1;
dfs1(1);
int diam1 = 1;
for(int i=1;i<=n;i++) if(h[i]>h[diam1]) diam1 = i;
dfs1(diam1);
int diam2 = diam1;
for(int i=1;i<=n;i++) if(h[i]>h[diam2]) diam2 = i;
while(diam2!=diam1){
diametru.push_back(diam2);
ap[diam2] = 1;
diam2 = tata[diam2];
}
ap[diam1] = 1;
diametru.push_back(diam1);
///Build solution
int ld = diametru.size();
for(int x:diametru) dfs2(x);
mx[0][0] = mxd[diametru[0]];
for(int i=1;i<ld;i++) mx[i][0] = MAX(mx[i-1][0], i + mxl[diametru[i]]);
//std::cout<<mx[1][0]<<" "<<mx[2][0]<<" "<<mx[3][0]<<"\n";
mx[ld-1][1] = mxd[diametru.back()];
for(int i=ld-2;i>=0;i--) mx[i][1] = MAX(mx[i+1][1], ld-i-1+mxl[diametru[i]]);
int ans = ld-1;
for(int i=1;i<ld;i++) {
ans = MIN(ans, MAX(MAX(mx[i-1][0], mx[i][1]), (mx[i-1][0]+1)/2 + (mx[i][1]+1)/2 + 1));
}
fout<<ans<<"\n";
}
int main() {
int t;
fin>>t;
while(t--) solve();
}