Skip to Content
CTRL K

City Attractions

Introducción

Sea tit_i el nodo al que va Gigel desde el nodo ii. Como el grafo formado por las aristas dirigidas i→tii \rightarrow t_i es un grafo funcional, podemos usar elevación binaria (binary jumping) o cualquier otro método eficiente para hallar el nodo final.

¡Ahora solo necesitamos hallar todos los tit_i y listo! Sin embargo, esto no es tan directo como suena…

Un problema más simple

Consideremos un problema más simple: supongamos que enraizamos el árbol en el nodo 11 y Gigel solo puede moverse hacia abajo en el árbol (sin preocuparnos por las hojas). En este problema, podemos hallar todos los tit_i (y a[ti]−dist(i,ti)a[t_i] - dist(i, t_i)) usando una simple DP en árboles:

Sea dp[i]dp[i] el nodo en el subárbol de ii (excluyendo ii mismo) tal que a[dp[i]]−dist(i,dp[i])a[dp[i]] - dist(i, dp[i]) se maximiza. Además, guardamos este valor en el arreglo de DP. Podemos hallar dp[i]dp[i] tomando el mejor entre cc y dp[c]dp[c] sobre todos los hijos cc de ii.

Este algoritmo corre en tiempo O(N)\mathcal{O}(N).

Hallar todos los tit_i

Obviamente, la solución del problema más simple no resuelve el problema general: ¡podríamos necesitar subir al padre de un nodo!

Para resolver esto, podemos primero hacer un DFS para hallar dpdp como se definió arriba, y luego un segundo DFS para permitir movernos fuera de nuestro subárbol. Ver el módulo de resolver para todas las raíces si no se está familiarizado con esta técnica. Esencialmente, hallamos el mejor destino desde ii si subimos al padre de ii y luego lo comparamos con dp[i]dp[i].

Después de hacer esto, dp[i]dp[i] es simplemente tit_i como queríamos.

Hallar el destino final

Hay dos formas de hallar la ubicación final de Gigel.

  1. Podemos implementar elevación binaria (binary jumping) sobre nuestro arreglo que contiene la siguiente ubicación
  2. Intentamos llegar a un ciclo, y luego tomamos nuestros saltos restantes módulo el tamaño del ciclo

El primer método es un poco más fácil de implementar, pero introduce un factor logarítmico.

Implementación 1

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

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	int n;
	ll k;
	cin >> n >> k;
 
	vector<int> a(n);
	for (int &i : a) { cin >> i; }
 
	vector<vector<int>> adj(n);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
 
	const array<int, 2> def = {-(n + 1), -1};
	vector<array<int, 2>> top(n, def);
	vector<array<int, 2>> sub(n, def);
 
	/** @return best next node in subtree of u */
	const auto get = [&](int u) -> array<int, 2> {
		return max(array<int, 2>{sub[u][0] - 1, sub[u][1]},
		           array<int, 2>{a[u] - 1, -u});
	};
 
	// calculamos el mejor vértice al que ir en el subárbol actual
	function<void(int, int)> dfs = [&](int u, int p) {
		for (const int v : adj[u]) {
			if (v == p) { continue; }
			dfs(v, u);
			sub[u] = max(sub[u], get(v));
		}
	};
 
	dfs(0, -1);
 
	vector<int> next_node(n);
 
	// calculamos el mejor vértice al que ir fuera del subárbol actual
	function<void(int, int)> reroot = [&](int u, int p) {
		next_node[u] = -max(top[u], sub[u])[1];
		array<int, 2> best = top[u];
		array<int, 2> alt = def;
		for (const int v : adj[u]) {
			if (v == p) { continue; }
			const array<int, 2> cur = get(v);
			if (cur > best) {
				alt = best, best = cur;
			} else if (cur > alt) {
				alt = cur;
			}
		}
 
		for (const int v : adj[u]) {
			if (v == p) { continue; }
			top[v] = get(v) == best ? alt : best;
			top[v][0]--;
			top[v] = max(top[v], array<int, 2>{a[u] - 1, -u});
			reroot(v, u);
		}
	};
 
	reroot(0, -1);
 
	int res = 0;
	for (int i = 0; i < 63; i++) {
		if ((k >> i) & 1) { res = next_node[res]; }
 
		vector<int> new_next(n);
		for (int j = 0; j < n; j++) { new_next[j] = next_node[next_node[j]]; }
 
		next_node = move(new_next);
	}
 
	cout << res + 1 << endl;
}

Implementación 2

Complejidad temporal: O(N)O(N)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	int n;
	ll k;
	cin >> n >> k;
 
	vector<int> a(n);
	for (int &i : a) { cin >> i; }
 
	vector<vector<int>> adj(n);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
 
	const array<int, 2> def = {-(n + 1), -1};
	vector<array<int, 2>> top(n, def);
	vector<array<int, 2>> sub(n, def);
 
	/** @return best next node in subtree of u */
	const auto get = [&](int u) -> array<int, 2> {
		return max(array<int, 2>{sub[u][0] - 1, sub[u][1]},
		           array<int, 2>{a[u] - 1, -u});
	};
 
	// calculamos el mejor vértice al que ir en el subárbol actual
	function<void(int, int)> dfs = [&](int u, int p) {
		for (const int v : adj[u]) {
			if (v == p) { continue; }
			dfs(v, u);
			sub[u] = max(sub[u], get(v));
		}
	};
 
	dfs(0, -1);
 
	vector<int> next_node(n);
 
	// calculamos el mejor vértice al que ir fuera del subárbol actual
	function<void(int, int)> reroot = [&](int u, int p) {
		next_node[u] = -max(top[u], sub[u])[1];
		array<int, 2> best = top[u];
		array<int, 2> alt = def;
		for (const int v : adj[u]) {
			if (v == p) { continue; }
			const array<int, 2> cur = get(v);
			if (cur > best) {
				alt = best, best = cur;
			} else if (cur > alt) {
				alt = cur;
			}
		}
 
		for (const int v : adj[u]) {
			if (v == p) { continue; }
			top[v] = get(v) == best ? alt : best;
			top[v][0]--;
			top[v] = max(top[v], array<int, 2>{a[u] - 1, -u});
			reroot(v, u);
		}
	};
 
	reroot(0, -1);
 
	int res = 0;
	if (k <= n) {
		for (int i = 0; i < k; i++) { res = next_node[res]; }
	} else {
		k -= n;
		for (int i = 0; i < n; i++) { res = next_node[res]; }
 
		vector<bool> vis(n);
		vector<int> path;
		while (!vis[res]) {
			vis[res] = true;
			path.push_back(res);
			res = next_node[res];
		}
 
		res = path[k % path.size()];
	}
 
	cout << res + 1 << endl;
}
Fundamentos