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"); | |
| } |
