Imaginate un arbol con raiz, de N nodos.
Enfocarse en una arista (u, v), donde u es el padre de v.
Decimos que (u, v) es “pesada” si el tamaño del subárbol de v es al menos la mitad del tamaño del subárbol de u. En tal caso, decimos que v es un “hijo pesado” de u.
A las aristas que no son pesadas las llamamos “livianas”.
obs: un nodo no puede tener más de un hijo pesado.
A los caminos maximales compuestos completamente por aristas pesadas les decimos “caminos pesados”.
obs: en un camino desde la raíz hasta una hoja puede haber a lo sumo log2(N) aristas livianas. (por qué? porque si recorremos el camino de arriba hacia abajo, al cruzar una arista liviana se divide el tamaño del subarbol a la mitad. esto no puede pasar muchas veces)
obs: si un nodo está a una gran profundidad en el grafo, el camino desde la raiz hacia este va a estar compuesto de largas seguidillas de aristas pesadas interrumpidas por unas pocas aristas livianas. Si imaginamos un tipito que va bajando desde la raiz, este se va moviendo mucho tiempo por el mismo camino pesado y de vez en cuando cruza una arista liviana para cambiar de camino pesado.
int const maxn = 100000;
int n;
vector<int> g[maxn];
int p[maxn]; // padre
int h[maxn]; // hijo pesado (o -1 si no tiene)
int t[maxn]; // tamaño de subarbol
void dfs(int u) {
t[u] = 1;
for (int v : g[u]) if (v != p[u]) {
p[v] = u;
dfs(v);
t[u] += t[v];
}
}
void decompose(int root) {
forn(u, n) h[u] = -1;
p[root] = -1;
dfs(root);
forn(v, n) {
if (int u = p[v]; u != -1 && t[v]*2 >= t[u]) {
h[u] = v;
}
}
}
Problema interactivo. Te dan un árbol con raíz, de N nodos (
N <= 10^5). Hay un nodo secreto x que hay que descubrir. Para lograrlo podes hacer dos tipos de consultas:
- d(u): dado un nodo u te responden la distancia de u a x
- s(u): dado un nodo u te responden el siguiente nodo en el camino hacia x. u debe ser ancestro de x. si no, te dan wrong answer inmediatamente.
Se pueden realizar a lo sumo 36 consultas.
Nos paramos en la raiz y nos vamos a ir acercando iterativamente al nodo x.
Considera el camino desde la raiz hasta x. Este camino contiene a lo sumo
log2(N) <= 17aristas livianas.Entre medio de cada par de aristas livianas hay un camino pesado.
Si logramos procesar cada camino pesado y cada arista pesada con una sola consulta, lograriamos el limite de consultas del problema.
Si sabemos que el camino arranca metiendose por un camino pesado pero en algun momento se sale, es posible calcular en que punto se sale haciendo una consulta de distancia en el primer nodo del camino y tambien en el ultimo. (hacemos dos consultas de tipo d(u)).
Una vez que sabemos en que nodo se sale del camino pesado, puede haber mas de una arista liviana por la que se puede salir. Ahi hay que hacer una consulta de tipo s(u).
Esto haria en el peor caso
17 + 2 * 18 = 53consultas.Siendo un poco mas ingenioso se puede calcular la consulta de distancia del inicio del camino pesado usando los resultados anteriores.
Esto baja la cantidad de consultas a
17 + 18 = 35en el peor caso.
int const maxn = 200100;
int n;
vector<int> g[maxn];
int h[maxn], p[maxn], t[maxn];
// ... dfs(), decompose() ...
int d(int u) { // implementa la consulta d(u) del interactivo
cout << "d " << (u+1) << "\n" << flush;
int ans; cin >> ans; return ans;
}
int s(int u) { // implementa la consulta s(u) del interactivo
cout << "s " << (u+1) << "\n" << flush;
int ans; cin >> ans; return ans-1;
}
int main() {
cin >> n;
forn(i, n-1) {
int u, v; cin >> u >> v; --u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
decompose(0);
int top = 0;
int d_top = d(top);
while (true) {
int steps_btm = 0;
int btm = top;
while (h[btm] != -1) cerr << btm << "\n", btm = h[btm], steps_btm++;
int d_btm = d(btm);
int steps_mid = d_top - (d_top + d_btm - steps_btm) / 2;
int mid = top;
forn(_, steps_mid) mid = h[mid];
int d_mid = d_top - steps_mid;
if (d_mid == 0) {
cout << "! " << mid+1 << "\n";
return 0;
}
top = s(mid);
d_top = d_mid - 1;
}
}
Cada nodo tiene O(log(N)) aristas livianas en su camino hacia la raiz. Esto se
puede dar vuelta para llegar a la siguiente observacion:
obs: Si iteramos por todo el subarbol de cada hijo liviano, visitamos cada
nodo O(log(N)) veces.
Esto significa que podemos hacer algoritmos bastante brutos y van a ser eficientes, siempre y cuando no recorramos el subarbol de cada hijo pesado muchas veces.
Hay un arbol con raiz, de N nodos (
N <= 2*10^5), donde cada nodo tiene un color. Por cada nodo, nos preguntan cuantos colores distintos aparecen en su subarbol.
Tomamos algun camino pesado, y vamos iterando de abajo hacia arriba, manteniendo un conjunto de colores.
En cada paso insertamos el color del nodo actual y recorremos los subarboles de todos los hijos livianos del nodo actual, insertando sus colores en el conjunto.
Como todo el subarbol del hijo pesado ya estaba insertado en el conjunto, en todo momento lo que tenemos es el conjunto de colores del subarbol del nodo actual, lo cual nos permite responder su cantidad de colores.
Ahora repetimos este algoritmo para cada camino pesado (consideramos nodos que no son hijos pesados ni tienen hijo pesado como un camino en si mismo).
Para analizar la complejidad, notemos que por cada nodo, insertamos su color en
un conjunto una vez al iterar su camino pesado y una vez por cada arista liviana
que está en su camino hacia la raíz. O sea, a lo sumo log2(N)+1 veces.
Esto significa que cada nodo se inserta O(log(N)) veces, por lo que el
algoritmo realiza a lo sumo O(N log(N)) inserciones en un conjunto. Si usamos
unordered_set, obtenemos exactamente esa complejidad.
int const maxn = 200000;
int n;
vector<int> g[maxn];
int p[maxn], h[maxn], t[maxn];
// ... dfs(), decompose() ...
vector<int> post; // post-orden
int tl[maxn], tr[maxn]; // rango de cada subarbol en el post-orden
void dfs2(int u) {
tl[u] = post.size();
for (int v : g[u]) if (v != p[u])
dfs2(v);
post.push_back(u);
tr[u] = post.size();
}
int c[maxn]; //color
int main() {
cin >> n;
forn(u, n) cin >> c[u];
forn(i, n-1) {
int u, v; cin >> u >> v; --u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
decompose(0);
dfs2(0);
vector<int> ans(n, -1);
for (int u : post) if (ans[u] == -1) {
unordered_set<int> colors;
while (true) {
colors.insert(c[u]);
// inserto los colores del subarbol de cada hijo liviano
for (int v : g[u]) if (v != p[u] && v != h[u])
forr(i, tl[v], tr[v])
colors.insert(c[post[i]]);
ans[u] = colors.size();
// si v es un hijo pesado, subo. si no, freno.
if (p[u] != -1 && h[p[u]] == u) u = p[u];
else break;
}
}
forn(u, n) cout << ans[u] << " \n"[u==n-1];
}
Una forma común de aprovechar la descomposicion en aristas livianas y pesadas es en problemas donde queremos simular que en cada nodo del árbol comienza una fichita y esta va a ir caminando hacia la raíz.
Simulando directamente, esto toma tiempo proporcional a la suma de las
profundidades de todos los nodos, que puede ser O(N^2)
En cambio, si pudieramos simular el trayecto de cada fichitas por un camino
pesado en O(1) y solo pagaramos las aristas individualmente en el caso de ser
livianas, entonces tendriamos un algoritmo O(N log(N)).
Esta misma idea se puede aplicar para el problema anterior.
La idea va a ser que podemos mantener un set de colores en cada nodo, donde cada elemento del set representa una “ficha” correspondiente a cada nodo.
Al cruzar una arista pesada, movemos todas las fichas en O(1) haciendo un
std::swapostd::movedel set del hijo pesado hacia el set del padreAl cruzar una arista liviana simplemente movemos las fichas una por una al set del nodo padre.
// ... definir grafo, arreglos y funciones de la descomposicion ...
vector<int> post;
void dfs2(int u) {
for (int v : g[u]) if (v != p[u])
dfs2(v);
post.push_back(u);
}
int c[maxn]; //color
int main() {
cin >> n;
forn(u, n) {
cin >> c[u];
}
forn(i, n-1) {
int u, v; cin >> u >> v; --u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
decompose(0);
dfs2(0);
vector<set<int>> colors(n);
vector<int> ans(n);
for (int u : post) {
// muevo todas las fichitas del hijo pesado en O(1)
if (h[u] != -1) colors[u] = move(colors[h[u]]);
// agrego mi fichita
colors[u].insert(c[u]);
// muevo fichitas de los hijos livianos una por una
for (int v : g[u]) if (v != p[u] && v != h[u])
for (int x : colors[v])
colors[u].insert(x);
ans[u] = colors[u].size();
}
forn(u, n) cout << ans[u] << " \n"[u==n-1];
}
Comentario de implementacion:
No hace falta guardarse el post-orden y procesar posteriormente. Se puede hacer lo mismo escribiendo el codigo directamente en el dfs. De esa manera queda un codigo un poco mas corto y simple.
Para la solucion anterior es un poco mas complicado de lograr.
La aplicacion mas famosa de esta descomposicion es su uso para responder consultas de suma/max/gcd (o cualquier operacion asociativa) en caminos de un arbol, donde cada nodo tiene un valor.
obs: un camino cualquiera solo toca a lo sumo 2*(log2(N)+1) caminos
pesados. (Porque un camino u–v esta contenido en la union entre los caminos
u–raiz y v–raiz, que tocan a lo sumo log2(N)+1 cada uno)
La idea es construir una estructura de datos que permite responder consultas de rangos en cada camino pesado. (Por ejemplo segment tree)
Para responder una consulta sobre un camino, lo descomponemos en las partes que caen en distintos caminos pesados y respondemos cada consulta usando la estructura del camino pesado correspondiente.
En mas detalle, imaginate que queremos calcular una consulta a lo largo del
camino entre dos nodos u y v.
obs: Si u y v estan en el mismo camino pesado, entonces el camino
u–v es esta contenido en este camino pesado, y podemos responder la
consulta mediante una consulta en rango.
obs: Si u y v estan en distintos caminos pesados, el camino de u–v
contiene completamente al menos una de dos cosas:
u–c[u]v–c[v]En particular, el de mayor profundidad entre c[u] y c[v] siempre esta
contenido. O sea que:
Si c[v] es el mas profundo, podemos partir la consulta sobre el camino
u–v en dos partes:
u–p[c[v]] (contenido en un mismo camino pesado)c[v]–vEn cambio, si c[u] es el mas profundo, podemos partir en:
u–c[u]p[c[u]]–v (contenido en un mismo camino pesado)Aca vemos una forma de implementar pero no es necesariamente la mas corta o la mas eficiente, si no que apunta a ser entendible. Hay implementaciones de calidad de competencia en distintos lados en Internet (KACTL, cp-algorithms, el-vasito-icpc, etc.)
Aparte, nos limitamos al caso de operaciones conmutativas. Resolver el caso no-conmutativo no es mucho mas dificil, pero complica la implementacion y distrae de la idea principal. En particular, la implementacion que sigue es para hacer suma pero deberia ser directo adaptarla para otras operaciones asociativas y conmutativas (max, min, gcd, etc.)
Veamos la inicializacion de la estructura.
A cada camino pesado le asignamos un id unico, que es el id del nodo de mas arriba del camino. Aparte, en cada nodo guardamos el id del camino pesado al que pertenece.
Despues construimos un segment tree sobre cada camino pesado (para esto primero calculamos el tamaño del camino en cantidad de nodos y despues asignamos valores al segment tree segun los nodos que componen el camino)
obs: la posicion de un nodo en su camino pesado se puede calcular a partir de su profundidad en el arbol.
int const maxn = 100000;
int n; // cantidad de nodos
vector<int> g[maxn]; // arbol como lista de adyacencia
int val[maxn]; // valor de cada nodo
int p[maxn]; // p[u] = padre de u en el arbol
int h[maxn]; // h[u] = hijo pesado de u (o -1 si no tiene)
int t[maxn]; // t[u] = tamaño de subarbol de u
int c[maxn]; // c[u] = comienzo del camino pesado al que pertenece u
int d[maxn]; // d[u] = profundidad de u en el arbol
vector<int> pre; // pre-orden
struct Segtree {
vector<int> data;
void init(int n) { /* ... */ }
int query(int l, int r) { /* ... */ }
int update(int i, int x) { /* ... */ }
};
Segtree ts[maxn];
void dfs(int u) {
pre.push_back(u);
t[u] = 1;
for (int v : g[u]) if (v != p[u]) {
p[v] = u;
d[v] = d[u] + 1;
dfs(v);
t[u] += t[v];
}
}
void decompose(int root) {
forn(u, n) h[u] = -1;
d[root] = 0;
p[root] = -1;
dfs(root);
// asignamos ids a los caminos pesados
// iteramos en preorden para poder propagar c[u] "hacia abajo"
for (int v : pre) {
if (int u = p[v]; u != -1 && t[v]*2 >= t[u]) {
h[u] = v;
c[v] = c[u];
} else {
c[v] = v;
}
}
// construimos segment tree en cada camino pesado
forn(u, n) if (c[u] == u) {
int len = 1;
for (int v = u; v != -1; v = h[v]) {
len += 1;
}
ts[u].init(len);
for (int v = u; v != -1; v = h[v]) {
ts[u].update(d[v] - d[u], val[v]);
}
}
}
Una consulta sobre un camino se calcula recursivamente, separando en los casos que hablamos antes.
int query(int u, int v) {
if (c[u] == c[v]) { // camino contenido en un camino pesado
int const w = c[u];
int l = d[u] - d[w];
int r = d[v] - d[w];
if (l > r) swap(l, r);
return ts[w].query(l, r+1);
}
if (d[c[u]] < d[c[v]]) { // c[v] es mas profundo
return query(u, p[c[v]]) + query(c[v], v);
} else { // c[u] es igual o mas profundo
return query(u, c[u]) + query(p[c[u]], v);
}
}
Esta estructura tambien permite actualizar los valores.
void update(int u, int x) {
int w = c[u];
ts[w].update(d[u] - d[w], x);
}
Para soportar operaciones no conmutativas, en cada camino pesado hay que guardar un segment tree con los elementos en orden inverso.
Despues, en el caso base de la consulta, se debe usar ese segment tree en orden inverso cuando
l > r(aparte de ajustar los indices adecuadamente).