最低共同祖先解决问题

解题思路:
lca+dfs。
注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,q;
vector<int> t1[N];
int type[N]; 
int a[N][23];
int fa[N][21];
int dep[N];
void dfs(int v,int f){
	fa[v][0] = f;
	dep[v] = dep[f] + 1;
	for(int i=1;i<=23;i++){
		a[v][i] = a[f][i];
		a[v][type[v]]++;
	}
	for(int k=1;(1 << k) <= dep[v] - 1;k++){
		fa[v][k] = fa[fa[v][k-1]][k-1];
	}
	for(int i = 0;i<t1[v].size();i++){
		int u = t1[v][i];
		if( u != f) dfs(u,v);
	}
} 

int lca(int u,int v){
	if(dep[u] < dep[v]){
		swap(u,v);
	}
	for(int k=20;k>=0;k--){
		if(dep[v]+(1 << k) <= dep[u]){
			u = fa[u][k];
		}
	}
	if(u == v) return u;
	for(int k=20;k>=0;k--){
		if(fa[u][k] != fa[v][k]){
			u = fa[u][k],v = fa[v][k];
		}
	}
	return fa[v][0];
	
}
int main(){
	//记住这两个优化输入输出的方法。 
	ios::sync_with_stdio(false);
    cin.tie(0);
    
	cin >> n >> q;
	int tmp = 0;
	for(int i=1;i<=n;i++){
		cin >> tmp;
		type[i] = tmp;
	}
	for(int k=0;k<n-1;k++){
		int i,j;
		cin >> i >>j;
		t1[i].push_back(j);
		t1[j].push_back(i); 
	}
	dfs(1,0);
	int begin,end;
	while(q--){
		cin >> begin >> end;
		int fa = lca(begin,end);
		int ans = 0;
		for(int i=1;i<=22;i++){
			int val = a[begin][i] + a[end][i] - 2*a[fa][i] + (i == type[fa]);
			if(val > 0) ans++;
		} 
		cout << ans << endl;
	}
	return 0;
}