#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,k,s,t,a[N],ans[N],de[N],num[N],f[N][20],log2n;
vector<int> e[N];
vector<pair<int,int>> q[N];
void dfs(int u){
    for (int &v:e[u]){
        if (v==f[u][0]) continue;
        f[v][0]=u;
        de[v]=de[u]+1;
        dfs(v);
    }
}
void dfs1(int u){
    num[a[u]]++;//u点奶牛种类的数量+1 
    for (auto &i:q[u]){ //遍历该位置所有的查询，并更新答案 
        if (i.second<0) ans[-i.second]-=num[i.first];
        else ans[i.second]+=num[i.first];
    }
    for (int &v:e[u]){
        if (v==f[u][0]) continue;
        dfs1(v);
    }
    num[a[u]]--;//回溯时减去影响 
}
int lca(int s,int t){
    if (de[s]<de[t]) swap(s,t);
    for (int w=de[s]-de[t],o=0;w;w>>=1,++o)
        if (w&1) s=f[s][o];
    if (s==t) return s;
    for (int j=log2n;j>=0;--j)
        if (f[s][j]!=f[t][j]) s=f[s][j],t=f[t][j];
    return f[s][0];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;++i) cin>>a[i];
    for (int i=1;i<n;++i){
        cin>>s>>t;
        e[s].push_back(t);
        e[t].push_back(s);
    }
    dfs(1);
    log2n=log2(n);
    for (int j=1;j<=log2n;++j)
        for (int i=1;i<=n;++i)
            f[i][j]=f[f[i][j-1]][j-1];
    for (int i=1;i<=m;++i){
        cin>>u>>v>>k;
        int p=lca(u,v); 
       	//一组询问拆分为4个单点询问,使用vector插入到对应位置  
        q[u].push_back({k,i});//在u位置查询根到u种类为k的奶牛数量，查询id为i 
        q[v].push_back({k,i});//在v位置查询根到v种类为k的奶牛数量，查询id为i 
        q[p].push_back({k,-i});//-i 标记该位置查询出来的奶牛数量要减去 
        q[f[p][0]].push_back({k,-i});
    }
    dfs1(1);
    for (int i=1;i<=m;++i)
        cout<<(ans[i]?'1':'0');
}

按老师的做法1思路写的：

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, m;
bool ans[N];
int logn, tot, pos[N], head[N], sz[N], f[N][20], de[N];
int c[N];
vector<int> b[N];
struct que
{
    int x, y, id;
};
vector<que> a[N];
struct node
{
    int y, next;
}e[N];
void adde(int x, int y)
{
    e[++tot] = {y, head[x]};
    head[x] = tot;
}
void dfs(int fa, int u)
{
    pos[u] = ++tot;
    sz[u] = 1;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].y;
        if (v == fa)
            continue;
        f[v][0] = u;
        de[v] = de[u] + 1;
        dfs(u,v);
        sz[u] += sz[v];
    }
}
int lca(int x, int y)
{
    if (de[x] < de[y])
        swap(x, y);
    for (int i = 0, p = de[x] - de[y]; p; i++, p >>= 1)
        if (p & 1)
            x = f[x][i];
    if (x == y)
        return x;
    for (int i = logn; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
void add(int x, int y)
{
    for (; x <= n; x += x & (-x))
        c[x] += y;
}
int query(int x)
{
    int ans = 0;
    for (; x; x -= x & (-x))
        ans += c[x];
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        b[x].push_back(i);
    }
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        adde(x, y);
        adde(y, x);
    }
    tot = 0;
    dfs(0, 1);
    logn = log2(n);
    for (int j = 1; j <= logn; j++)
        for (int i = 1; i <= n; i++)
            f[i][j] = f[f[i][j-1]][j-1];
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        a[z].push_back((que){x, y, i});
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i].empty())
            continue;
        for (int j = 0; j < (int)b[i].size(); j++)
        {
            add(pos[b[i][j]], 1);
            add(pos[b[i][j]] + sz[b[i][j]], -1);
        }
        for (int j = 0; j < (int)a[i].size(); j++)
        {
            que now = a[i][j];
            int LCA = lca(now.x, now.y);
            ans[now.id] = query(pos[now.x]) + query(pos[now.y]) - query(pos[LCA]) - query(pos[f[LCA][0]]);
        }
        for (int j = 0; j < (int)b[i].size(); j++)
        {
            add(pos[b[i][j]], -1);
            add(pos[b[i][j]] + sz[b[i][j]], 1);
        }
    }
    for (int i = 1; i <= m; i++)
        cout << ans[i];
    return 0;
}