Solução Informática Intermediário - Semana 57

Por Samyra Almeida

Para resolver esse problema é necessário conhecimento sobre o algoritmo de LCA(Menor Ancestral Comum).

Vamos tratar o mapa como uma árvore, onde os restaurantes são os nós e as estradas as arestas.

Com isso, para resolvermos as consultas do tipo 1, durante a DFS também vamos guardar um vetor dist[] = distância dos nós a raiz da árvore. Assim, a distância entre $u$ e $v$ é igual a $dist[u] + dist[v] - 2*dist[LCA(u, v)]$ , onde $dist[LCA(u, v)]$ $=$ distância do $LCA$ de $u$ e $v$ a raiz da árvore, e como ela aparece duas vezes, tanto em $dist[u]$ como em $dist[v]$ , também precisamos descontá-la duas vezes.

Agora para resolvermos a consulta do tipo 2, chamar a função $find(u,$ $k)$ que retorna o k-ésimo nó no caminho de $u \rightarrow raiz$ . Para montarmos o algoritmo dessa função iremos utilizar a mesma tabela utilizada para descobrirmos o $LCA$ entre dois nós, como sabemos que o nó está $k$ níveis acima de $u$ , basta irmos subindo $u$ até que encontremos o nó.

Mas antes de procurarmos o k-ésimo nó no caminho de $u \rightarrow v$ , vamos analisar os três possíveis casos

O k-ésimo nó é igual ao $lca$ entre $u$ e $v$ : para checar esse caso, basta calcularmos a diferença entre os níveis de $u$ e o $lca$ e checamos e é igual a, se sim, imprimimos o $lca$ de $u$ e $v$ , caso contrário, continuamos o algoritmo.
O k-ésimo nó está antes do $lca$ entre $u$ e $v$ : nesse caso basta chamarmos o $find(u,$ $k - 1)$ e imprimimos o nó que a função retornará.
O k-ésimo nó está depois do $lca$ entre $u$ e $v$ : chame de $a$ o k-ésimo nó no caminho entre $u$ e $v$ , nesse caso, precisamos saber quantos nós $a$ está acima de $v$ . Para isso basta calcularmos quantos nós existem no caminho de $u$ até $v$ e descontarmos $k$ .

Segue código solução para maior compreensão:

	#include <bits/stdc++.h>
	#define F first
	#define S second

	using namespace std;

	typedef pair<int, int> pii;
	const int maxn = 10010, maxl = 20; // declaro os limites

	// declaro as variáveis que vou utilizar
	int n, q;
	int ancestral[maxn][maxl];
	int dist[maxn], nivel[maxn];

	vector<pii> graph[maxn];

	void dfs(int u, int pai)
	{
	if(pai != -1) nivel[u] = nivel[pai] + 1; // calculo o meu nível

	ancestral[u][0] = p; // coloco meu pai na tabela

	for(auto v: graph[u]) // percorro meus filhos
	{
	if(v.S == pai) continue; // se meu filho é igual o meu pai, continuo
	// se não

	dist[v.S] = dist[u] + v.F; // calculo minha distância á raiz

	dfs(v.S, u); // chamo a dfs
	}
	}

	void tabela() // monto a tabela dos ancestrais
	{
	memset(ancestral, -1, sizeof ancestral);
	memset(dist, 0, sizeof dist);
	memset(nivel, 0, sizeof nivel);

	dfs(1, -1);

	for(int j = 1 ; j <= maxl ; ++j)
	{
	for(int i = 1 ; i <= n ; ++i)
	{
	if(ancestral[i][j - 1] != -1)
	{
	ancestral[i][j] = ancestral[ancestral[i][j - 1]][j - 1];
	}
	}
	}
	}

	int LCA(int u, int v) // procuro o LCA entre u e v
	{
	if(nivel[u] < nivel[v]) swap(u, v);

	for(int i = maxl - 1 ; i >= 0 ; --i)
	{
	if(nivel[u]-(1<<i) >= nivel[v])
	{
	u = ancestral[u][i];
	}
	}

	if(u == v) return u;

	for(int i = maxl - 1 ; i >= 0 ; --i)
	{
	if(ancestral[u][i] != -1 && ancestral[v][i] != ancestral[u][i])
	{
	u = ancestral[u][i];
	v = ancestral[v][i];
	}
	}

	return ancestral[u][0];
	}


	int find(int u, int k) // procuro o k-ésimo nó no caminho para a raiz
	{
	for(int i = maxl - 1 ; i >= 0 ; --i) // passo por todos os niveis da tabela
	{
	if(k - (1<<i) >=0) // se eu ainda não achei o nó
	{
	u = ancestral[u][i]; // subo 2^i níveis
	k -= (1<<i); // diminuo minha distância ao nó
	}
	}

	return u;
	}

	int main()
	{
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n;

	for(int i = 1 ; i < n ; ++i) // monto a árvore
	{
	int u, v, c;
	cin >> u >> v >> c;

	graph[u].push_back(pii(c, v));
	graph[v].push_back(pii(c, u));
	}

	tabela(); // monto a tabela dos ancestrais

	string s;

	for(int i = 1 ; i <= q ; ++i)
	{
	int id, u, v;

	cin >> u, v;

	if(id == 1) cout << dist[u] + dist[v] - 2*dist[LCA(u, v)] << "\n";

	else
	{
	int k;
	cin >> k;

	int lca = LCA(u, v);

	int diferenca_niveis = nivel[u] - nivel[lca] + 1; // calculo a diferença entre os níveis do lca e u

	if(k == diferenca_niveis) // significa que o lca de u e v está a k níveis de distancia de u
	{
	cout << lca << "\n";
	}

	else if(k < diferenca_niveis) // se o lca estiver no caminho de u até o lca
	{ // procuro quem esta a k - 1 níveis acima de u.

	cout << find(u, k-1) << "\n";
	}

	else // nesse caso, o k-ésimo nó do caminho de u -> v esta depois do lca, ou seja,
	{ // no caminho de v até o lca.

	cout << find(b, diferenca_niveis + nivel[v] - nivel[lca] - k) << "\n";
	}
	}
	}
	return 0;
	}

view raw

noic-solucao-intermediario-s57.cpp

hosted with ❤ by GitHub