Cod sursa(job #1901334)

Utilizator prazillaPrazilla prazilla Data 3 martie 2017 21:18:24
Problema Revolta Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 3.03 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 100000;
const int kInf = numeric_limits<int>::max() / 2;

int n;
vector<int> chain, G[kMaxN];
int D[2][kMaxN], V[2][kMaxN], H[2][kMaxN];

void bfs(int s, int e)
{
	queue<int> Q;
	D[e][s] = 0;
	Q.push(s);
	while (!Q.empty()) {
		s = Q.front();
		Q.pop();
		for (auto x : G[s]) {
			if (D[e][x] == -kInf) {
				D[e][x] = D[e][s] + 1;
				Q.push(x);
			}
		}
	}
}

void reconstruct(int s, int e)
{
	if (D[e][s] == 0) {
		chain.push_back(s);
		return;
	} else {
		for (auto x : G[s]) {
			if (D[e][s] == D[e][x] + 1) {
				reconstruct(x, e);
				chain.push_back(s);
				return;
			}
		}
	}
}

void computeV(int s, int e)
{
	for (auto x : G[s]) {
		if (D[e][x] == D[e][s] + 1) {
			computeV(x, e);
			if (V[e][x] >= V[e][s]) V[e][s] = V[e][x] + 1;
		}
	}
}

int main()
{
	freopen("revolta.in", "rt", stdin);
	freopen("revolta.out", "wt", stdout);

	int t;
	scanf("%d", &t);

	while (t--) {
		int root = 0, aux, r = kInf;
		scanf("%d", &n);
		chain.clear();
		for (int i = 0; i < n; ++i) G[i].clear();
		for (int i = 1; i < n; ++i) {
			int a, b;
			scanf("%d %d", &a, &b);
			G[a].push_back(b);
			G[b].push_back(a);
		}
		for (int i = 0; i < n; ++i) D[0][i] = -kInf;
		bfs(0, 0);
		for (int i = 1; i < n; ++i) {
			if (D[0][i] > D[0][root]) root = i;
		}
		for (int i = 0; i < n; ++i) D[0][i] = -kInf;
		bfs(root, 0);
		aux = root;
		for (int i = 0; i < n; ++i) {
			if (D[0][i] > D[0][aux]) aux = i;
		}
		reconstruct(aux, 0); //diameter is stored in chain
		for (int i = 0; i < n; ++i) V[0][i] = 0;
		computeV(root, 0); //store the depth of the subtree with root i in V[e][i]
	
		// -----------
		for (int i = 0; i < n; ++i) D[1][i] = -kInf;
		bfs(chain[chain.size() - 1], 1);
		for (int i = 0; i < n; ++i) V[1][i] = 0;
		computeV(chain[chain.size() - 1], 1);
		// -------
/*		for (int i = 0; i < n; ++i) fprintf(stderr, "%d ", D[0][i]);
		fprintf(stderr, "\n");	
		
		for (int i = 0; i < n; ++i) fprintf(stderr, "%d ", V[0][i]);
		fprintf(stderr, "\n");	
		
		for (int i = 0; i < n; ++i) fprintf(stderr, "%d ", D[1][i]);
		fprintf(stderr, "\n");	
		
		for (int i = 0; i < n; ++i) fprintf(stderr, "%d ", V[1][i]);
		fprintf(stderr, "\n\n");	
*/		
		H[0][0] = 0;
		for (int i = 1; i < chain.size(); ++i) {
			int o = 0;
			for (auto x : G[chain[i]]) {
				if (x != chain[i - 1] && i + 1 < chain.size() && 
					x != chain[i + 1]) o = max(o, V[0][x]);
			}
			H[0][i] = max(H[0][i - 1], D[0][chain[i]] + o);
		}
		H[1][chain.size() - 1] = 0;
		for (int i = chain.size() - 2; i >= 0; --i) {
			int o = 0;
			for (auto x : G[chain[i]]) {
				if (x != chain[i + 1] &&
					i - 1 >= 0 && x != chain[i - 1]) o = max(o, V[1][x]);
			}
			H[1][i] = max(H[1][i + 1], D[1][chain[i]] + o);
		}
//		for (int i = 0; i < chain.size(); ++i) fprintf(stderr, "%d %d\n", H[0][i], H[1][i]);
//		fprintf(stderr, "\n");
		for (int i = 1; i < chain.size(); ++i) {
			int d1 = H[0][i];
			int d2 = H[1][i - 1];
			if (d1 > d2) swap(d1, d2);
			if ((d1 + 1) / 2 > (d2 + 1) / 2) r = min(r, d2 + 1);
			else r = min(r, d2);
		}
		printf("%d\n", r);			
	}

	return 0;
}