求出lca。 再加一个cnt数组维护从根节点到i点，各种零食出现的次数。 则每种零食在任意两点u，v出现的次数是： $res[i] = cnt[u][i] + cnt[v][i] - cnt[l][i] - cnt[fa[l][0]][i];$ ```cpp #include<bits/stdc++.h> #define endl '\n' using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; int n,q; vector<vector<int>> fa; vector<int> dep; vector<vector<int>> g; vector<vector<int>> cnt; vector<int> c; void initlca(int x){ for(int i=0;i<=20;i++) fa[x][i+1] = fa[fa[x][i]][i]; for(auto y:g[x]){ if(y==fa[x][0]) continue; dep[y] = dep[x]+1; fa[y][0] = x; for(int i=1;i<=20;i++){ cnt[y][i] = cnt[x][i] + (c[y]==i); } initlca(y); } } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int d=dep[x]-dep[y],i=0;d;d>>=1,i++){ if(d&1) x = fa[x][i]; } if(x==y) return x; for(int i=20;i>=0;i--){ if(fa[x][i]!=fa[y][i]) x = fa[x][i],y = fa[y][i]; } return fa[x][0]; } void solve(){ cin>>n>>q; fa = vector<vector<int>>(n+1,vector<int>(25,0)); dep = vector<int>(n+1); g = vector<vector<int>>(n+1); cnt = vector<vector<int>>(n+1,vector<int>(21));//从根节点到i节点的路径，包含的各种零食的数量 c = vector<int>(n+1); for(int i=1;i<=n;i++) cin>>c[i]; cnt[1][c[1]] = 1; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } initlca(1); while(q--){ int u,v; cin>>u>>v; int l = lca(u,v); vector<int> res(21,0); int ans = 0; for(int i=1;i<=20;i++){ res[i] = cnt[u][i] + cnt[v][i] - cnt[l][i] - cnt[fa[l][0]][i]; if(res[i] !=0) ans++; } cout<<ans<<endl; } } int main(){ ifstream test_file("0in.txt"); if (test_file) { freopen("0in.txt", "r", stdin); freopen("0output.txt", "w", stdout); } std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0); int T = 1; #ifdef MULTI_TEST cin>>T; #endif while(T--){ solve(); } return 0; } ```