Cod sursa(job #2709012)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 19 februarie 2021 17:15:00
Problema Revolta Scor 100
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 2.08 kb
#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();
}