cubraoscaminhosnoic.cpp

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