Skip to Content
CTRL K

New Barns

Pista 1

La mayor distancia desde un nodo es siempre hacia un extremo de un diámetro del árbol. Después de agregar un nodo, ¿cómo podemos mantener el diámetro de su árbol?

Respuesta a la pista 1

Consideremos usar el diámetro antes de agregar este nodo para hallar el diámetro después de agregar el nodo en cuestión.

Explicación

Editorial oficial (C++) 

Consideremos responder todas las consultas online. Como se indica en la Pista 1, la mayor distancia desde un nodo dado es hacia un extremo de un diámetro de nuestro árbol actual. Ahora el problema se reduce a llevar el diámetro de cada árbol dentro de nuestro grafo después de agregar un nodo.

Observemos que si agregamos una hoja al árbol que se convierte en un extremo de nuestro nuevo diámetro, entonces el otro extremo de nuestro nuevo diámetro es uno de los extremos de nuestro diámetro anterior. Para entender por qué es así, consideremos disponer el árbol de la siguiente manera:

Grafo de ejemplo

Digamos que agregamos un hijo al nodo 11. Ahora tenemos un nuevo diámetro que empieza en ese hijo, y necesitamos hallar un extremo adecuado. Notemos que siempre es óptimo elegir un extremo del diámetro actual porque si hubiera una mejor opción dentro de uno de los “subárboles”, sería el extremo del diámetro anterior.

Con este hecho, podemos mantener fácilmente el diámetro de cada árbol de nuestro grafo online. Hallar la distancia entre cada par de nodos se puede hacer usando binary lifting.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log{N})

#include <bits/stdc++.h>
using namespace std;
 
class Tree {
  private:
	const int q, log2dist;
	vector<vector<int>> up;
	vector<pair<int, int>> diameter;
	vector<int> root;
	vector<int> dep;
	int curr = -1;
 
  public:
	Tree(int q)
	    : q(q), log2dist(ceil(log2(q))), up(log2dist, vector<int>(q)), diameter(q),
	      root(q), dep(q) {}
 
	/** @return the LCA of nodes u and v */
	int lca(int u, int v) {
		if (dep[u] < dep[v]) { swap(u, v); }
		for (int i = log2dist - 1; i >= 0; i--) {
			if (((dep[u] - dep[v]) >> i) & 1) { u = up[i][u]; }
		}
		if (u == v) { return u; }
		for (int i = log2dist - 1; i >= 0; i--) {
			if (up[i][u] != up[i][v]) {
				u = up[i][u];
				v = up[i][v];
			}
		}
		return up[0][u];
	}
 
	/** @return the distance betweens nodes u and v */
	int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
 
	/** adds the given node into the tree it belongs to */
	void add_node(int par) {
		curr++;
		if (par == -2) {
			diameter[curr] = {curr, curr};
			for (int i = 0; i < log2dist; i++) { up[i][curr] = curr; }
			root[curr] = curr;
		} else {
			up[0][curr] = par;
			for (int i = 1; i < log2dist; i++) {
				up[i][curr] = up[i - 1][up[i - 1][curr]];
			}
 
			root[curr] = root[par];
			dep[curr] = dep[par] + 1;
 
			const auto [a, b] = diameter[root[curr]];
			int dist_a = dist(curr, a);
			int dist_b = dist(curr, b);
			int cur_dist = dist(a, b);
			if (dist_a > cur_dist) {
				diameter[root[curr]] = {a, curr};
			} else if (dist_b > cur_dist) {
				diameter[root[curr]] = {b, curr};
			}
		}
	}
 
	/** @return the furthest distance from node u */
	int query_dist(int u) {
		const auto [a, b] = diameter[root[u]];
		return max(dist(u, a), dist(u, b));
	}
};
 
int main() {
	freopen("newbarn.in", "r", stdin);
	freopen("newbarn.out", "w", stdout);
	int q;
	cin >> q;
	Tree tree(q);
	for (int i = 0; i < q; i++) {
		char type;
		int node;
		cin >> type >> node;
		node--;
		if (type == 'B') {
			tree.add_node(node);
		} else {
			cout << tree.query_dist(node) << "\n";
		}
	}
}
Fundamentos