觉得有用的话点个赞支持一下吧QWQ

这个题题意可简单概括为询问一棵树上的路径中有多少个不同的数

思路：注意到商品种类很少，那我们可以暴力枚举每个商品出现的个数，如果不为0

不同数的个数就+1

我们定义cnt[j][i]数组表示从根节点出发，到节点j中，商品i出现的次数

cnt[j][i]=j的父节点中商品i出现的个数+自身所包含的商品

cnt[j][i]=cnt[fa[j][0]][i];
cnt[j][arr[j]]++;

因此在询问一条路径时，我们就能用类似（lca题目，距离里面的思想），只要商品出现

次数大于0，那么商品就是存在的

c++代码如下

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][20];
int q[N];

int cnt[N][25],arr[N];      //arr[i]记录的是每个编号里是几号商品
bool st[N];                 //点有没有走过，因为完善cnt数组要用dfs

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}


void bfs(int root)              //照搬模板题里的预处理
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0;
    q[0] = root;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                for (int k = 1; k <= 19; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)              //照搬模板
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 19; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 19; k >= 0; k -- )
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

//特判一下，如果p里面的商品是当前的i，那就减多了，在加回来
int check(int p,int i){    
    if (arr[p]==i)  return 1;
    else return 0;
}

int cal(int p,int a,int b){              
    int ans=0;
    for(int i=1;i<=20;i++){                  //遍历每个商品，统计每个商品出现的次数
        int tmp=cnt[a][i]+cnt[b][i]-2*cnt[p][i]+check(p,i);
        if(tmp>0)  ans++;           //大于0，答案就++
    }
    return ans;
}

void dfs(int u){                        //对树进行dfs
    st[u]=true;
    for(int i=h[u];~i;i=ne[i]){

        int j=e[i];
        if (st[j])  continue;
        for(int i=1;i<=20;i++){
            cnt[j][i]=cnt[fa[j][0]][i];        //每一个商品都要用上述方法完善
        }
        cnt[j][arr[j]]++;
        dfs(j);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
    }
    int root = 1;
    memset(h, -1, sizeof h);

    for (int i = 0; i < n-1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    cnt[1][arr[1]]++;
    bfs(root);
    dfs(root);                     //到此，预处理全部完成
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);          
        printf("%d\n",cal(p,a,b));   //找到公共祖先后执行的操作
    }

    return 0;
}