Sloth Naptime

Explicación

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

Básicamente el enunciado pregunta si, dado un camino de un nodo de inicio a un nodo final en un árbol, hasta dónde viajará el perezoso si tiene una cantidad fija de energía, y cada arista del camino tiene un costo de energía.

Sabemos que el perezoso siempre intentará moverse hacia arriba desde el nodo de inicio $\texttt{st}$ hasta el ancestro común más bajo de los nodos de inicio y fin $\texttt{lca}$ , y luego moverse hacia abajo desde el ancestro común más bajo hacia el nodo final $\texttt{end}$ .

Sea $\texttt{dist}(i, j)$ la distancia del nodo $i$ al nodo $j$ .

Así, si el perezoso tiene una cantidad de energía $e$ , hay 3 casos separados:

$e \geq \texttt{dist}(dist(\texttt{st}, \texttt{end})$ . En este caso el resultado será que el perezoso llega al final.
$e < \texttt{dist(\texttt{st}, \texttt{end})}$ y $e < \texttt{dist(\texttt{st}, \texttt{lca})}$ en cuyo caso el resultado será que el perezoso llega al $e$ -ésimo padre de $\texttt{st}$ .
$e < \texttt{dist(\texttt{st}, \texttt{end})}$ y $e \geq \texttt{dist(\texttt{st}, \texttt{lca})}$ en cuyo caso el resultado será que el perezoso llega al $(e - \texttt{dist(\texttt{st}, \texttt{lca}))}$ -ésimo padre de $\texttt{end}$ .

Así, primero podemos ejecutar un DFS una vez para encontrar la profundidad de cada nodo.

Luego podemos crear una matriz $\texttt{anc}$ para guardar los ancestros de cada nodo, donde $\texttt{anc[i][j]}$ es el $2^j$ -ésimo ancestro del nodo $i$ .

Después de eso, podemos usar binary lifting para responder cada consulta encontrando el ancestro común más bajo de los nodos de inicio y fin, y luego encontrando el nodo correcto al que llegará el perezoso.

Implementación

JavaC++


import java.io.*;
import java.util.*;
public class SlothNaptime {
	public static final int MAXN = (int)3e5 + 5;
	public static final int LOGN = (int)(Math.log(MAXN) / Math.log(2)) + 1;
	public static ArrayList<Integer>[] adj = new ArrayList[MAXN];
	// anc[i][j] is the 2^j-th parent of i.
	public static int[][] anc = new int[MAXN][LOGN];
	public static int[] depth = new int[MAXN];
 
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		int N = io.nextInt();
		for (int i = 0; i < MAXN; i++) { adj[i] = new ArrayList<>(); }
		for (int i = 0; i < N - 1; i++) {
			int a = io.nextInt() - 1;
			int b = io.nextInt() - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
 
		dfs(0, 0);
		int Q = io.nextInt();
		for (int i = 1; i <= Q; i++) {
			int start = io.nextInt() - 1;
			int end = io.nextInt() - 1;
			int energy = io.nextInt();
			int lca = LCA(start, end);
			int moveUpLen = depth[start] - depth[lca];
			int moveDownLen = depth[end] - depth[lca];
			int result;
			if (energy <= moveUpLen) {
				// moves up from start towards the lca.
				result = jump(start, energy) + 1;
			} else if (energy <= moveUpLen + moveDownLen) {
				// moves up from start to the lca, then goes down towards end.
				result = jump(end, moveDownLen - (energy - moveUpLen)) + 1;
			} else {
				// reaches the end.
				result = end + 1;
			}
			System.out.println(result);
		}
	}
 
	public static void dfs(int node, int par) {
		anc[node][0] = par;
		depth[node] = depth[anc[node][0]] + 1;
 
		// initializes binary jumping for the current node.
		for (int lvl = 1; lvl < LOGN; lvl++) {
			anc[node][lvl] = anc[anc[node][lvl - 1]][lvl - 1];
		}
		for (int next : adj[node]) {
			if (next != par) dfs(next, node);
		}
	}
 
	// jump(i, j) returns jth ancestor of node i.
	public static int jump(int node, int level) {
		for (int i = 0; i < LOGN; i++) {
			if ((level & (1 << i)) > 0) { node = anc[node][i]; }
		}
		return (node > -1) ? node : 0;
	}
 
	// lca(i, j) returns least common ancestor of nodes i and j.
	public static int LCA(int a, int b) {
		if (depth[a] < depth[b]) {
			int tempA = a;
			a = b;
			b = tempA;
		}
 
		a = jump(a, depth[a] - depth[b]);
		if (a == b) { return a; }
		for (int i = LOGN - 1; i >= 0; i--) {
			int newA = anc[a][i];
			int newB = anc[b][i];
			if (newA != newB) {
				a = newA;
				b = newB;
			}
		}
		return anc[a][0];
	}
 
	// CodeSnip{Kattio}
}


#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 3e5 + 5;
const int LOGN = log2(MAXN) + 1;
 
int depth[MAXN];
// anc[i][j] is the 2^j-th parent of i.
int anc[MAXN][LOGN];
vector<int> adj[MAXN];
 
void dfs(int node, int par) {
	anc[node][0] = par;
	depth[node] = depth[anc[node][0]] + 1;
	// initializes binary jumping for the current node.
	for (int i = 1; i < LOGN; i++) { anc[node][i] = anc[anc[node][i - 1]][i - 1]; }
	for (int next : adj[node]) {
		if (next != par) { dfs(next, node); }
	}
}
 
// jump(i, j) returns jth ancestor of node i
int jump(int node, int level) {
	for (int i = 0; i < LOGN; i++) {
		if (level & (1 << i)) { node = anc[node][i]; }
	}
	return (node > -1) ? node : 0;
}
 
// lca(i, j) returns least common ancestor of nodes i and j.
int LCA(int a, int b) {
	if (depth[a] < depth[b]) { swap(a, b); }
	a = jump(a, depth[a] - depth[b]);
	if (a == b) { return a; }
	for (int i = LOGN - 1; i >= 0; i--) {
		int newA = anc[a][i];
		int newB = anc[b][i];
		if (newA != newB) { a = newA, b = newB; }
	}
	return anc[a][0];
}
 
int main() {
	int N;
	int Q;
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int a;
		int b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	dfs(0, 0);
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		int start, end, energy;
		cin >> start >> end >> energy;
		start--;
		end--;
		int lca = LCA(start, end);
		int path1 = depth[start] - depth[lca];
		int path2 = depth[end] - depth[lca];
		int result;
		if (energy <= path1) {
			// moves up from start towards the lca.
			result = jump(start, energy) + 1;
		} else if (energy <= path1 + path2) {
			// moves up from start to the lca, then goes down towards end.
			result = jump(end, path2 - (energy - path1)) + 1;
		} else {
			// reaches the end.
			result = end + 1;
		}
		cout << result << "\n";
	}
}