Solução Informática - Nível Avançado - Semana 19

Solução por Pedro Racchetti

Conhecimentos utilizados:

Para esse problema, primeiro temos que perceber que para qualquer caminho, podemos simplesmente usar o menor ancestral comum (LCA) entre os dois extremos, se considerarmos a raiz como um nó qualquer (iremos usar o $1$ , a título de implementação).

Podemos então perceber que se considerarmos a sub-árvore do LCA $X$ de um caminho, e algum outro caminho com o LCA $Y$ de altura menor que a altura de $X$ , e um dos pontos extremos de $Y$ estiver na sub-árvore de $X$ , não precisamos incluir $X$ no conjunto resposta! Portanto, quando processarmos um caminho, podemos verificar se qualquer um dos dois extremos já foram marcados. Se não, inserimos o LCA no conjunto resposta, e marcamos todos os vértices da sub-árvore dele.

Esse algoritmo porém fica muito demorados. Para acelerá-lo, podemos linearizar a árvore da seguinte maneira: guardaremos uma variável $timer$ . Sempre que chamarmos uma nova recursão na DFS na vértice $f$ , incrementamos o $timer$ por 1, e guardaremos esse valor no vetor $tin[f]$ . Quando sair de uma DFS, guardaremos o $timer$ no vetor $tout[f]$ . Nessa linearização, uma vértice $x$ está na sub-árvore de $y$ se $tin[y] \leq tin[x] \leq tout[y]$ . Podemos usar essa propriedade, para usarmos uma BIT de marcação, com esse vetor. Sempre que adicionarmos um LCA no conjunto, podemos fazer um update de valor $1$ na posição $tin[LCA]$ na BIT, e -1 na posição $tout[LCA] + 1$ . Para verificarmos se um caminho $i$ ja foi marcado, basta checar com uma query se a posição $tin[a_i]$ ou $tin[b_i]$ é maior que ou igual à 1.

Segue o código, comentado, para melhor compreensão:

	#include<bits/stdc++.h>
	using namespace std;
	const int MAXN = 1e5 + 10;
	typedef long long ll;
	int bit[MAXN];
	int T;

	void update(int idx, ll val){

	while(idx <= T){
	bit[idx] += val;
	idx += (idx&-idx);
	}

	}
	ll query(int idx){
	ll ans = 0;
	while(idx > 0){
	ans += bit[idx];
	idx -= (idx&-idx);
	}
	return ans;
	}

	vector<int> grafo[MAXN];
	int dp[25][MAXN];
	int tin[MAXN], tout[MAXN], altura[MAXN];
	void dfs(int x, int p){
	tin[x] = ++T;
	for(int i = 1; i <= 21; i++){
	dp[i][x] = dp[i-1][dp[i-1][x]];
	}
	for(int i = 0; i < grafo[x].size(); i++){
	int viz = grafo[x][i];
	if(viz == p) continue;
	altura[viz] = altura[x] + 1;
	dp[0][viz] = x;
	dfs(viz, x);
	}
	tout[x] = T;
	}

	int LCA(int a, int b){
	if(altura[a] < altura[b]) swap(a, b);
	int dist = altura[a] - altura[b];
	for(int k = 0; k <= 21; k++ ){
	if(dist&(1<<k)) a= dp[k][a];
	}
	if(a == b) return a;
	for(int k = 21; k >= 0; k--){
	if(dp[k][a] == dp[k][b]) continue;
	a = dp[k][a];
	b = dp[k][b];
	}
	return dp[0][a];
	}
	bool cmp(pair<int, int> a, pair<int, int> b){
	// essa funcao sera usada na ordenacao, para que ordenemos os caminhos pela maior altura
	return altura[a.first] > altura[b.first];
	}
	int n;
	vector<int> ans;
	pair<int, int > caminhos[MAXN], pontos[MAXN];
	int main(){
	scanf("%d", &n);
	for(int i = 1; i < n; i++){
	int u, v;
	scanf("%d %d", &u, &v);
	//inicializamos a arvore
	grafo[u].push_back(v);
	grafo[v].push_back(u);
	}
	//Inicializamos a tabela esparsa para o LCA
	//e as alturas dos caminhos
	dfs(1, 0);
	int m;
	scanf("%d" , &m);
	for(int i = 0; i < m; i++){
	int a, b;
	scanf("%d %d", &a, &b);
	//iremos guardar os caminhos com o LCA e os pontos que os compoem
	caminhos[i] = make_pair(LCA(a, b), i);
	pontos[i] = make_pair(a, b);
	}
	//Ordenamos os caminhos pela maior altura do lca
	sort(caminhos, caminhos + m, cmp);

	for(int i = 0; i < m; i++){
	int a = pontos[caminhos[i].second].first, b = pontos[caminhos[i].second].second;
	int lc = caminhos[i].first;
	//verificamos se esses pontos estão em alguma sub-árvore já marcada, os ignoramos
	if(query(tin[a]) >= 1\|\| query(tin[b]) >= 1 ) continue;
	//inserimos esse lca no conjunto resposta
	ans.push_back(lc);
	update(tin[lc], 1);
	update(tout[lc] + 1, -1);
	}
	//imprimimos o conjunto resposta
	printf("%d\n", ans.size());
	for(int i = 0; i < ans.size(); i++) printf("%d ",ans[i] );
	printf("\n");
	}

view raw

cubraoscaminhosnoic.cpp

hosted with ❤ by GitHub