P3603 雪辉 被我用 神秘复杂度 过掉之后，这个题也用同样复杂度过掉了。

这个块长不能根号，但调到 2000 的时候跑的飞快，一个点 800ms 左右。

#include <cmath>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
struct E
{
    int v, t;
} e[80001];
int n, m, c, p, o, K, L[512], R[512], T[40050], a[40050], z[40050],
    d[40050], f[40050], s[40050], t[40050], b[40050], k[40050], h[40050];
bitset<40001> B[512];
void A(int u, int v)
{
    e[++c] = {v, h[u]};
    h[u] = c;
}
void X(int u)
{
    s[u] = 1;
    for (int i = h[u], v; i; i = e[i].t)
        if (!d[v = e[i].v])
        {
            d[v] = d[f[v] = u] + 1;
            X(v);
            s[u] += s[v];
            if (s[v] > s[z[u]])
                z[u] = v;
        }
}
void Y(int u, int g)
{
    t[k[b[u] = ++p] = u] = g;
    if (z[u])
        Y(z[u], g);
    for (int i = h[u], v; i; i = e[i].t)
        if ((v = e[i].v) != f[u] && v != z[u])
            Y(v, v);
}
bitset<40001> Q(int l, int r)
{
    bitset<40001> q;
    if (T[l] == T[r])
    {
        for (int i = l; i <= r; ++i)
            q[a[k[i]]] = 1;
        return q;
    }
    for (int i = l; i <= R[T[l]]; ++i)
        q[a[k[i]]] = 1;
    for (int i = T[l] + 1; i < T[r]; ++i)
        q |= B[i];
    for (int i = L[T[r]]; i <= r; ++i)
        q[a[k[i]]] = 1;
    return q;
}
int main()
{
    scanf("%d%d", &n, &m);
    K = 2000;
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i), b[o++] = a[i];
    sort(b, b + o);
    o = unique(b, b + o) - b;
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b, b + o, a[i]) - b + 1;
    for (int i = 1, u, v; i < n; ++i)
        scanf("%d%d", &u, &v), A(u, v), A(v, u);
    X(d[1] = 1);
    Y(1, 1);
    for (int i = 1; i <= n; ++i)
        B[T[i] = (i - 1) / K + 1][a[k[i]]] = 1;
    for (int i = 1; i <= T[n]; ++i)
        L[i] = (i - 1) * K + 1, R[i] = min(i * K, n);
    for (int i = 0, l = 0, x, y; i < m; ++i)
    {
        bitset<40001> q;
        scanf("%d%d", &x, &y);
        x ^= l;
        while (t[x] != t[y])
        {
            if (d[t[x]] < d[t[y]])
                swap(x, y);
            q |= Q(b[t[x]], b[x]);
            x = f[t[x]];
        }
        if (b[x] > b[y])
            swap(x, y);
        q |= Q(b[x], b[y]);
        printf("%d\n", l = q.count());
    }
    return 0;
}