Descomposición Heavy-Light

Supongamos que queremos soportar las siguientes operaciones sobre un árbol:

Actualizar todos los nodos a lo largo del camino del nodo $x$ al nodo $y$ .
Consultar la suma, el máximo, el mínimo, o cualquier otra operación que cumpla la propiedad asociativa a lo largo del camino del nodo $x$ al nodo $y$ .

La descomposición Heavy-Light (HLD) soporta ambas operaciones de forma eficiente. Hacerlas de forma naive puede ser lento en árboles grandes, pero HLD descompone el árbol en caminos para permitir actualizaciones y consultas en tiempo logarítmico.

Recursos
Fuente	Recurso	Notas
cp-algo	HLD	Para una implementación alternativa, ver más abajo
CF	galen_colin - HLD	blog + video para USACO Cowland. El binary jumping no es necesario, igual.

Consultas en árboles en O(NQ)

Esto es por qué no hay que proponer problemas donde $\Theta(Q\sqrt N\log N)$ es lo intencionado…

Tutorial

Definiciones

Un hijo heavy de un nodo es el hijo con el subárbol más grande enraizado en ese hijo.
Un hijo light de un nodo es cualquier hijo que no es el hijo heavy.
Una arista heavy conecta un nodo con su hijo heavy.
Una arista light conecta un nodo con cualquiera de sus hijos light.
Un camino heavy es un camino maximal y contiguo formado solo por aristas heavy. El conjunto de todos los caminos heavy cubre todos los nodos del árbol. Observar que en HLD no hay noción de “caminos light”; las aristas light simplemente conectan caminos heavy entre sí.

Propiedades

Cualquier camino del nodo $x$ al nodo $y$ en el árbol puede pasar por a lo sumo $\mathcal{O}(\log N)$ aristas light.

Demostración

Considerar un camino del nodo $x$ al nodo $y$ . Este camino se puede partir en un camino del nodo $x$ a $LCA(x,y)$ y un camino del nodo $y$ a $LCA(x,y)$ . Como $LCA(x,y)$ es un ancestro de ambos extremos, solo hace falta demostrar que el camino de cualquier nodo hacia cualquiera de sus ancestros pasa por $\mathcal{O}(\log N)$ aristas light.

Supongamos que una arista light conecta un nodo padre $u$ y un nodo hijo $v$ . Por la definición de arista light, $v$ debe ser un hijo light. Esto implica que $u$ tiene un hijo heavy con un tamaño de subárbol mayor o igual que el de $v$ . Por lo tanto, el tamaño del subárbol enraizado en $u$ debe ser al menos el doble del tamaño del subárbol enraizado en $v$ , ya que contiene tanto el subárbol de $v$ como el del hijo heavy.

Como el tamaño del subárbol de un nodo no puede exceder la cantidad total de nodos, $N$ , este proceso de duplicación puede ocurrir a lo sumo $\mathcal{O}(\log N)$ veces al subir desde cualquier nodo hasta la raíz. Por lo tanto, hay a lo sumo $\mathcal{O}(\log N)$ aristas light en el camino de $x$ a $LCA(x,y)$ y en el camino de $y$ a $LCA(x,y)$ . En total, el camino de $x$ a $y$ contiene $\mathcal{O}(\log N)+\mathcal{O}(\log N)=\mathcal{O}(\log N)$ aristas light.

Un camino heavy solo se puede romper al cruzar una arista light; de lo contrario, el camino heavy simplemente continuaría. Por esto, sabemos que hay a lo sumo ${O}(\log N)$ caminos heavy en cualquier camino de un nodo arbitrario $x$ a un nodo arbitrario $y$ .

Además, usando un Árbol de Segmentos (o una estructura similar), podemos procesar consultas sobre un segmento contiguo de cualquier cadena heavy en tiempo $\mathcal{O}(\log N)$ .

Como el proceso requiere hacer $\mathcal{O}(\log N)$ operaciones de Árbol de Segmentos, el tiempo total de una consulta o actualización de camino es $\mathcal{O}(\log N) \times \mathcal{O}(\log N) = \mathcal{O}(\log^2 N)$ . Por lo tanto, podemos responder $Q$ consultas en tiempo $\mathcal{O}(Q \log^2 N)$ .

Acá hay una animación de cómo funciona el algoritmo:

Implementación

Recursos
Fuente	Recurso	Notas
CF	AI-Cash - HLD Implementation
CF	adamant - Easiest HLD with subtree queries	no está completo
Benq	Complete HLD Implementation	implementación completa siguiendo los dos artículos de arriba, con modificaciones menores

Abajo hay una implementación de ejemplo de la descomposición Heavy-Light basada en los recursos de arriba. Ver la solución de abajo, además de las soluciones de Subtrees & Paths y Query on a tree again!, para ejemplos de cómo se puede usar esta implementación.

C++


#include <bits/stdc++.h>
using namespace std;
 
template <class T, bool VALS_IN_EDGES> class HLD {
  private:
	int N, R, tim = 0;  // n, root node, time
	vector<vector<int>> adj;
	vector<int> par, siz, depth, rt, pos;  // parent, size, depth, root, position arrays
	LazySegtree<T> segtree;                // Modify as needed
 
	/** Compute the size of each subtree and set parent-child relationship
	 * Subtree of node v corresponds to segment [ pos[v], pos[v] + sz[v] ) */
	void dfs_sz(int v) {
		if (par[v] != -1) adj[v].erase(find(adj[v].begin(), adj[v].end(), par[v]));
		for (int &u : adj[v]) {
			par[u] = v, depth[u] = depth[v] + 1;
			dfs_sz(u);
			siz[v] += siz[u];
			if (siz[u] > siz[adj[v][0]]) swap(u, adj[v][0]);
		}
	}
 
	/** Assign positions for nodes
	  * Path from v to the last vertex in ascending heavy path
	    corresponds to [ pos[rt[v]], pos[v] ] */
	void dfs_hld(int v) {
		pos[v] = tim++;
		for (int u : adj[v]) {
			rt[u] = (u == adj[v][0] ? rt[v] : u);
			dfs_hld(u);
		}
	}
 
	/** process all heavy path and combine their results */
	template <class B> void process(int u, int v, B op) {
		for (; rt[u] != rt[v]; v = par[rt[v]]) {
			if (depth[rt[u]] > depth[rt[v]]) swap(u, v);
			op(pos[rt[v]], pos[v]);
		}
		if (depth[u] > depth[v]) swap(u, v);
		op(pos[u] + VALS_IN_EDGES, pos[v]);
	}
 
  public:
	HLD(vector<vector<int>> adj_, int _R)
	    : N(adj_.size()), R(_R), adj(adj_), par(N, -1), siz(N, 1), depth(N), rt(N),
	      pos(N), segtree(vector<ll>(N, 0ll))  // modify if need
	{
		rt[R] = R;
		dfs_sz(R);
		dfs_hld(R);
	}
 
	T query_path(int u, int v) {
		T res = 0;  // default value, modify depending on problem
		process(u, v, [&](int l, int r) {
			res = max(res, segtree.range_max(l, r));  // modify depending on problem
		});
		return res;
	}
 
	void modify_node(int u, T val) { segtree.set(pos[u], val); }
 
	void modify_subtree(int v, T val) {
		segtree.range_update(pos[v] + VALS_IN_EDGES, pos[v] + siz[v] - 1,
		                     Query{ADD, val});  // modify if need
	}
};

Path Queries II

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Path Queries II	Fácil		en el módulo

Explicación

Podemos etiquetar cada arista como heavy o light, y después usar un árbol de segmentos para llevar el máximo de cada cadena heavy.

Ahora, para cambiar el valor del nodo $i$ a $x$ , basta con actualizar el valor en el árbol de segmentos. Para consultar el valor máximo en el camino de $a$ a $b$ , primero hallamos el ancestro común más bajo. Combinamos el camino de $a$ a $lca(a,b)$ y el camino de $b$ a $lca(a,b)$ para obtener la respuesta.

Implementación

Complejidad temporal: $\mathcal{O}(\log^2N)$ por consulta

C++


#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Segment Tree}
/** A data structure that can answer point update & range max queries. */
template <class T> class MaxSegmentTree {
  private:
	// const T DEFAULT = std::numeric_limits<T>().max();
	const T DEFAULT = 0;
 
	int len;
	vector<T> segtree;
 
  public:
	MaxSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}
 
	void set(int ind, T val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = std::max(segtree[ind], segtree[ind ^ 1]);
		}
	}
 
	T range_max(int start, int end) {
		T max = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { max = std::max(max, segtree[start++]); }
			if (end % 2 == 1) { max = std::max(max, segtree[--end]); }
		}
		return max;
	}
};
// EndCodeSnip
 
// BeginCodeSnip{HLD}
template <class T, bool VALS_IN_EDGES> class HLD {
  private:
	int N, R, tim = 0;  // n, root node, time
	vector<vector<int>> adj;
	vector<int> par, siz, depth, rt, pos;  // parent, size, depth, root, position arrays
	MaxSegmentTree<T> segtree;             // Modify as needed
 
	/** Compute the size of each subtree and set parent-child relationship
	 * Subtree of node v corresponds to segment [ pos[v], pos[v] + sz[v] ) */
	void dfs_sz(int v) {
		if (par[v] != -1) adj[v].erase(find(adj[v].begin(), adj[v].end(), par[v]));
		for (int &u : adj[v]) {
			par[u] = v, depth[u] = depth[v] + 1;
			dfs_sz(u);
			siz[v] += siz[u];
			if (siz[u] > siz[adj[v][0]]) swap(u, adj[v][0]);
		}
	}
 
	/** Assign positions for nodes
	  * Path from v to the last vertex in ascending heavy path
	    corresponds to [ pos[rt[v]], pos[v] ] */
	void dfs_hld(int v) {
		pos[v] = tim++;
		for (int u : adj[v]) {
			rt[u] = (u == adj[v][0] ? rt[v] : u);
			dfs_hld(u);
		}
	}
 
	/** process all heavy path and combine their results */
	template <class B> void process(int u, int v, B op) {
		for (; rt[u] != rt[v]; v = par[rt[v]]) {
			if (depth[rt[u]] > depth[rt[v]]) swap(u, v);
			op(pos[rt[v]], pos[v]);
		}
		if (depth[u] > depth[v]) swap(u, v);
		op(pos[u] + VALS_IN_EDGES, pos[v]);
	}
 
  public:
	HLD(vector<vector<int>> adj_, int _R)
	    : N(adj_.size()), R(_R), adj(adj_), par(N, -1), siz(N, 1), depth(N), rt(N),
	      pos(N), segtree(N)  // modify as needed
	{
		rt[R] = R;
		dfs_sz(R);
		dfs_hld(R);
	}
 
	T query_path(int u, int v) {
		T res = 0;  // default value, modify depending on problem
		process(u, v, [&](int l, int r) {
			res = max(res, segtree.range_max(l, r + 1));  // modify depending on problem
		});
		return res;
	}
 
	void modify_node(int u, T val) { segtree.set(pos[u], val); }
};
// EndCodeSnip
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	int n, q;
	cin >> n >> q;
	vector<int> v(n);
	vector<vector<int>> adj(n);
	for (int i = 0; i < n; i++) { cin >> v[i]; }
 
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		--a, --b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	HLD<int, 0> H(adj, 0);
 
	for (int i = 0; i < n; i++) { H.modify_node(i, v[i]); }
 
	while (q--) {
		int type, s, a, b, x;
		cin >> type;
		if (type == 1) {
			cin >> s >> x;
			--s;
			H.modify_node(s, x);
		} else if (type == 2) {
			cin >> a >> b;
			--a, --b;
			cout << H.query_path(a, b) << " ";
		}
	}
}

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Company Queries II	Fácil	LCA, HLD	Solución
Gold	Cow Land	Fácil	PURS, HLD	Solución
SPOJ	Query on a tree again!	Fácil	HLD	Solución
Gold	Milk Visits	Normal	HLD	Solución
Platinum	Disruption	Normal	HLD	Solución
HR	Subtrees & Paths	Normal	HLD, RURQ	Solución
Old Gold	Grass Planting	Normal	HLD, PURS	—
YS	Vertex Set Path Composite	Normal	HLD, SegTree	Solución
CF	Tree Queries	Difícil	HLD	—
CF	The Tree	Difícil	HLD	Solución
TLX	Tree Game	Difícil	HLD	—
JOI	2013 - Synchronization	Difícil	HLD	Solución
JOI	2018 - Cats or Dogs	Muy difícil	HLD	Solución