COCI 2008/2009

krtica.cpp

// COCI 2008/2009 - Krtica
// Lúcio Cardoso

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5+10;

int n;
int d[3][maxn], diam[2][maxn];
int ans, par, child;
int dist[maxn], pai[maxn];

bool mark[maxn];

vector<int> grafo[maxn];

void dfs(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		dfs(v, u);

		if (d[0][v]+1 > d[0][u]) d[2][u] = d[1][u], d[1][u] = d[0][u], d[0][u] = d[0][v]+1;
		else if (d[0][v]+1 > d[1][u]) d[2][u] = d[1][u], d[1][u] = d[0][v]+1;
		else if (d[0][v]+1 > d[2][u]) d[2][u] = d[0][v]+1;

		int dv = max(diam[0][v], d[0][v]+d[1][v]);

		if (dv > diam[0][u]) diam[1][u] = diam[0][u], diam[0][u] = dv;
		else if (dv > diam[1][u]) diam[1][u] = dv;
	}
}

void dfs2(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p || mark[v]) continue;

		dist[v] = dist[u]+1, pai[v] = u;
		dfs2(v, u);
	}
}

void rotate(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		int ant[5] = {d[0][u], d[1][u], d[2][u], diam[0][u], diam[1][u]};

		int dv = max(diam[0][v], d[0][v]+d[1][v]);

		if (d[0][v]+1 == d[0][u]) d[0][u] = d[1][u], d[1][u] = d[2][u];
		else if (d[0][v]+1 == d[1][u]) d[1][u] = d[2][u];

		if (max(diam[0][v], d[0][v]+d[1][v]) == diam[0][u]) diam[0][u] = diam[1][u];

		int du = max(diam[0][u], d[0][u]+d[1][u]);

		int aux = min(ans, max({dv, (dv+1)/2 + (du+1)/2 + 1, du}));

		if (aux < ans) ans = aux, par = u, child = v;

		if (d[0][u]+1 > d[0][v]) d[2][v] = d[1][v], d[1][v] = d[0][v], d[0][v] = d[0][u]+1;
		else if (d[0][u]+1 > d[1][v]) d[2][v] = d[1][v], d[1][v] = d[0][u]+1;
		else if (d[0][u]+1 > d[2][v]) d[2][v] = d[0][u]+1;

		if (du > diam[0][v]) diam[1][v] = diam[0][v], diam[0][v] = du;
		else if (du > diam[1][v]) diam[1][v] = du;

		rotate(v, u);

		d[0][u] = ant[0], d[1][u] = ant[1], d[2][u] = ant[2], diam[0][u] = ant[3], diam[1][u] = ant[4];
	}
}

int center(int u, int p)
{
	memset(mark, 0, sizeof mark);
	memset(dist, 0, sizeof dist);

	mark[p] = 1;
	dfs2(u, 0);

	int maior = -1, v;
	for (int i = 1; i <= n; i++)
		if (dist[i] > maior)
			maior = dist[i], v = i;

	dist[v] = 0, pai[v] = 0;
	dfs2(v, 0);

	maior = -1;
	for (int i = 1; i <= n; i++)
		if (dist[i] > maior)
			maior = dist[i], v = i;

	while (true)
	{
		if (dist[v] == (maior+1)/2) return v;

		v = pai[v];
	}
}

int main(void)
{
	cin >> n;

	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;

		grafo[u].push_back(v); grafo[v].push_back(u);
	}

	ans = 1e9+10;
	dfs(1, 0); rotate(1, 0);

	int c1 = center(child, par);
	int c2 = center(par, child);

	cout << ans << "\n";
	cout << par << " " << child << "\n";
	cout << c1 << " " << c2 << "\n";
}