Nos dan hasta dos rectángulos para dividir nuestro camino. ¿Cuál es la forma más lógica de partir un camino en un árbol enraizado?

Consideremos un grafo estrella con aristas $(1, 2)$, $(1, 3)$ y $(1, 4)$. Una disposición posible es colocar nuestro primer nodo en $(1, 1)$, y colocar todos los demás nodos sobre una diagonal. Se puede ver una visualización aquí .

¿Podemos generalizar esta idea?

Explicación

Podemos partir cualquier camino según el LCA de los dos extremos. Más concretamente, si $l$ es el ancestro común más bajo de nuestros nodos $a$ y $b$, entonces partimos nuestro camino en el camino de $a$ a $l$, y el camino de $l$ a $b$. Al partir el camino, podemos construir cualquier camino como dos caminos más pequeños entre un nodo y uno de sus ancestros.

Solo queda construir un esquema en el que un rectángulo pueda cubrir correctamente los nodos de un camino vertical. Consideremos el grafo de ejemplo de la segunda pista, donde construir un grafo con una diagonal funciona. Como se nos pide embeber nuestro grafo en una grilla de $N \times N$, podemos darnos el lujo de dar a cada nodo su propia columna y fila. Así, podemos pensar el caso de ejemplo de forma recursiva: en lugar de colocar nodos sobre una diagonal, podemos colocar subárboles sobre diagonales y particionar nuestra grilla de esa forma.

Sea $s_i$ el tamaño del subárbol actual, y supongamos que nuestro nodo está en $(x,y)$. Para la raíz (nodo 1), tenemos $s_i = n$ y $(x,y) = (1,1)$. Embebemos el subárbol en una grilla de $s_i \times s_i$ cuya esquina inferior izquierda está en $(x,y)$. Recursivamente, para cada uno de los hijos del nodo, asignamos una subgrilla dentro de ese cuadrado: el primer hijo y su subárbol ocupan un cuadrado en la esquina inferior derecha, y cada hijo siguiente se coloca “en diagonal” continuando hacia la esquina superior izquierda.

Con este embebido, cualquier camino vertical de nuestro árbol corresponde a un rectángulo alineado con los ejes con sus esquinas en los extremos de nuestro camino. Para entender por qué es así, consideremos crear nuestro rectángulo expandiéndolo a medida que recorremos desde el nodo de arriba hasta el nodo de abajo en nuestro camino. Nuestra esquina inferior izquierda permanece fija en nuestro nodo de arriba, y movemos nuestra esquina superior derecha a medida que recorremos hacia nuestro nodo de abajo. Como cada subgrilla embebida es disjunta de las demás, nuestra esquina superior derecha nunca cruzará hacia una subgrilla no intencionada, y estamos expandiendo estrictamente el rectángulo con cada movimiento. Así, nuestro rectángulo deseado tiene sus esquinas en los extremos de nuestro camino.

Por ejemplo, el grafo formado con aristas $(1, 2)$, $(1, 3)$, $(3, 4)$ y $(3, 5)$ se procesará de la siguiente forma:

• El nodo $1$ se coloca en $(1, 1)$ y ocupa la grilla de $(1, 1)$ a $(5, 5)$.
  • El nodo $2$ tiene un subárbol de tamaño $1$. Así, ocupa la celda $(5, 2)$.
  • El nodo $3$ tiene un subárbol de tamaño $3$. Así, ocupa la celda $(2, 3)$, y se procesa de forma recursiva.
• El nodo $3$ ocupa la grilla de $(2, 3)$ a $(4, 5)$.
  • El nodo $4$ tiene un subárbol de tamaño $1$. Así, ocupa la celda $(4, 4)$.
  • El nodo $5$ tiene un subárbol de tamaño $1$. Así, ocupa la celda $(3, 5)$.

Un ejemplo del caso de arriba se puede ver aquí .

Con eso en mente, nuestro algoritmo para procesar un camino involucra dos pasos: partir nuestro camino, y hallar un rectángulo adecuado para el camino vertical producido. La primera parte se puede hacer con cualquier algoritmo rápido de LCA de elección, y la implementación de abajo usa binary lifting. Para el segundo paso, nuestro rectángulo se construye a partir de los dos extremos de nuestro camino. Notemos que debemos asegurarnos de que nuestro LCA no se incluya en ambos rectángulos.

Implementación

Complejidad temporal: $\mathcal{O}((N+Q)\log{N})$

#include "grader.h"
#include <bits/stdc++.h>
 
using ll = long long;
 
constexpr int LG = 20;
 
std::vector<std::array<int, LG>> lift;
std::vector<int> dep, sub;
std::vector<std::vector<int>> adj;
std::vector<std::array<int, 2>> locs;
int n;
 
// returns the least common ancestor of u and v using binary lifting
int lca(int u, int v) {
	if (dep[u] < dep[v]) std::swap(u, v);
 
	int diff = dep[u] - dep[v];
	for (int k = LG - 1; k >= 0; k--) {
		if (diff & (1 << k)) { u = lift[u][k]; }
	}
 
	if (u == v) return u;
 
	for (int k = LG - 1; k >= 0; k--) {
		if (lift[u][k] != lift[v][k]) {
			u = lift[u][k];
			v = lift[v][k];
		}
	}
 
	return lift[u][0];
}
 
void addRoad(int a, int b) {
	if (!n) {
		n = getN();
		adj.resize(n);
		locs.resize(n);
		lift.resize(n);
		dep.resize(n);
		sub.resize(n);
	}
 
	adj[a].push_back(b);
	adj[b].push_back(a);
}
 
// calculating subtree sizes and binary lifts
void dfs1(int u, int p) {
	sub[u] = 1;
	for (int v : adj[u]) {
		if (v == p) continue;
		dep[v] = dep[u] + 1;
		lift[v][0] = u;
		for (int i = 1; i < LG; i++) { lift[v][i] = lift[lift[v][i - 1]][i - 1]; }
 
		dfs1(v, u);
		sub[u] += sub[v];
	}
}
 
int timer = 1;
 
// setting all the farm locations
void dfs2(int u, int p, int x1, int x2) {
	// timer is used instead of passing in y1 and y2 values for subgrid
	locs[u] = {x1, timer};
	setFarmLocation(u, x1, timer);
	timer++;
 
	// recursively embedding values, with first child occupying bottom-right
	// and last child occupying upper-left section of the diagonal
	int prev = x2 + 1;
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs2(v, u, prev - sub[v], prev - 1);
		prev -= sub[v];
	}
}
 
void buildFarms() {
	dfs1(0, -1);
	dfs2(0, -1, 1, n);
}
 
void notifyFJ(int a, int b) {
	int l = lca(a, b);
 
	// processes the path from anc to desc, where anc is an ancestor to desc
	// exclude indicates whether or not we have to exclude the ancestor node
	auto process_path = [&](int anc, int desc, bool exclude = false) {
		int x1 = locs[anc][0];
		int y1 = locs[anc][1];
		int x2 = locs[desc][0];
		int y2 = locs[desc][1];
		addBox(x1 + exclude, y1 + exclude, x2, y2);
	};
 
	if (l == a) {
		process_path(a, b);
	} else if (l == b) {
		process_path(b, a);
	} else {
		process_path(l, a);
		process_path(l, b, true);
	}
}