过了 $n \le 5000$ 和特殊性质 $A$ 的 $60pts$，剩余 WA 了，进队就差这 $40pts$。

现场代码：

/*
#include <cstdio>
using namespace std;
const int N = 500010;
const int LOGN = 20;
struct Edge {
    int to, nxt;
}edges[N << 1];
int occ[N];
int lis[N], k;
int fa[N][LOGN], depth[N];
int cnt[N];
int op[N], col[N];
int head[N], n, q, nedge;
inline void swap(int &x, int &y) {x ^= y; y ^= x; x ^= y;}
inline void addedge(int u, int v) {
    edges[++nedge].to = v;
    edges[nedge].nxt = head[u];
    head[u] = nedge;
}
inline int LCA(int x, int y) {
    if(depth[x] < depth[y]) swap(x, y);
    for(int i = LOGN - 1; i >= 0; --i)
        if((1 << i) <= depth[x] - depth[y]) x = fa[x][i];
    if(x == y) return x;
    for(int i = LOGN - 1; i >= 0; --i)
        if(fa[x][i] != fa[y][i]) {x = fa[x][i]; y = fa[y][i];}
    return fa[x][0];
}
inline void dfs(int u) {
    for(int i = 1; (1 << i) <= depth[u]; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = head[u]; i; i = edges[i].nxt) {
        int v = edges[i].to;
        if(fa[u][0] == v) continue;
        fa[v][0] = u; depth[v] = depth[u] + 1;
        dfs(v);
    }
}
int main() {
    freopen("keys.in", "r", stdin);
    freopen("keys.out", "w", stdout);
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; ++i) scanf("%d %d", &op[i], &col[i]);
    for(int i = 1; i < n; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        addedge(u, v); addedge(v, u);
    }
    dfs(1);
    while(q--) {
        int u, v; scanf("%d %d", &u, &v);
        int u0 = u, v0 = v;
        int lc = LCA(u, v); int dis = depth[u] + depth[v] - 2 * depth[lc] + 1;
//        printf("u=%d, v=%d, lc=%d\n", u, v, lc);
        k = 0;
        while(true) {
            lis[++k] = u;
            if(u == lc) break;
            u = fa[u][0];
        }
        while(v != lc) {lis[dis--] = v; v = fa[v][0];}
        for(int i = 1; i <= n; ++i) occ[i] = 0;
        dis = depth[u0] + depth[v0] - 2 * depth[lc] + 1;
        int ans = 0;
//        printf("dis=%d\n", dis);
        for(int i = 1; i <= dis; ++i) {
//            printf("path: u=%d, op=%d, col=%d\n", lis[i], op[lis[i]], col[lis[i]]);
            if(op[lis[i]] == 1) ++occ[col[lis[i]]];
            else if(occ[col[lis[i]]] > 0) {++ans; --occ[col[lis[i]]];}
        }
        printf("%d\n", ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
*/

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 500010;
const int M = N * 40;
const int Q = 1000010;
const int LOGN = 20;
const int inf = 1e9 + 10;
struct Edge {
    int to, nxt;
}edges[N << 1], edges2[N << 1];
struct Operation {
    int y, dir;
}oper[M]; int nopt;
struct Question {
    int x, y;
}que[Q]; int final_answer[Q];
int headque[Q], nxtque[Q];
int headop[N], nxtop[M];
vector<int> keys, money;
int lg[N];
int stk[N], par[N];
int sum[N], top[N], heavy[N], dfn2[N], siz[N], tim2;
int lis[N], k;
int dfn[N], out[N], depth[N], fa[N][LOGN], tim;
int op[N], col[N];
int nxtcol[N], headcol[N];
int head2[N], nedge2;
int head[N], n, q, nedge;
int Fenwick[N];
inline int lowbit(int x) {return x & -x;}
inline void modify(int x, int d) {
    while(x <= n) {
        Fenwick[x] += d;
        x += lowbit(x);
    }
}
inline int quest(int x) {
    int ret = 0;
    while(x) {
        ret += Fenwick[x];
        x -= lowbit(x);
    }
    return ret;
}
struct Solution1 {
    int sum, idx;
    bool operator < (const Solution1 &rhs) const {
        if(sum != rhs.sum) return sum < rhs.sum;
        return depth[idx] < depth[rhs.idx];
    }
}ST1[N][LOGN];
struct Solution2 {
    int sum, idx;
    bool operator > (const Solution2 &rhs) const {
        if(sum != rhs.sum) return sum > rhs.sum;
        return depth[idx] > depth[rhs.idx];
    }
}ST2[N][LOGN];
inline Solution1 min(Solution1 x, Solution1 y) {return x < y ? x : y;}
inline Solution2 max(Solution2 x, Solution2 y) {return x > y ? x : y;}
inline Solution1 query1(int l, int r) {
    int k = lg[r - l + 1];
    return min(ST1[l][k], ST1[r - (1 << k) + 1][k]);
}
inline Solution2 query2(int l, int r) {
    int k = lg[r - l + 1];
    return max(ST2[l][k], ST2[r - (1 << k) + 1][k]);
}
inline bool cmp(int x, int y) {return dfn[x] < dfn[y];}
inline void addedge(int u, int v) {
    edges[++nedge].to = v;
    edges[nedge].nxt = head[u];
    head[u] = nedge;
}
inline void addedge2(int u, int v) {
//    printf("addedge2(u=%d, v=%d)\n", u, v);
    edges2[++nedge2].to = v;
    edges2[nedge2].nxt = head2[u];
    head2[u] = nedge2;
}
inline void addoper(int l1, int r1, int l2, int r2) {
    oper[++nopt] = (Operation){l2, 1};
    nxtop[nopt] = headop[l1]; headop[l1] = nopt;
    oper[++nopt] = (Operation){l2, -1};
    nxtop[nopt] = headop[r1 + 1]; headop[r1 + 1] = nopt;
    oper[++nopt] = (Operation){r2 + 1, -1};
    nxtop[nopt] = headop[l1]; headop[l1] = nopt;
    oper[++nopt] = (Operation){r2 + 1, 1};
    nxtop[nopt] = headop[r1 + 1]; headop[r1 + 1] = nopt;
//    printf("addoper(l1=%d, r1=%d, l2=%d, r2=%d)\n", l1, r1, l2, r2);
}
inline void swap(int &x, int &y) {x ^= y; y ^= x; x ^= y;}
inline int LCA(int x, int y) {
    if(depth[x] < depth[y]) swap(x, y);
    for(int i = LOGN - 1; i >= 0; --i)
        if((1 << i) <= depth[x] - depth[y]) x = fa[x][i];
    if(x == y) return x;
    for(int i = LOGN - 1; i >= 0; --i)
        if(fa[x][i] != fa[y][i]) {x = fa[x][i]; y = fa[y][i];}
    return fa[x][0];
}
inline int jump(int x, int k) {
    for(int i = LOGN - 1; i >= 0; --i)
        if(k & (1 << i)) x = fa[x][i];
    return x;
}
inline void dfs0(int u) {
    dfn[u] = ++tim;
    for(int i = 1; (1 << i) <= depth[u]; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int i = head[u]; i; i = edges[i].nxt) {
        int v = edges[i].to;
        if(fa[u][0] == v) continue;
        fa[v][0] = u; depth[v] = depth[u] + 1;
        dfs0(v);
    }
    out[u] = tim;
}
inline void dfs(int u, int c) {
    sum[u] = sum[par[u]] + (col[u] == c ? (op[u] == 1 ? 1 : -1) : 0);
//    printf("sum[u=%d]=%d\n", u, sum[u]);
    siz[u] = 1; heavy[u] = 0;
    for(int i = head2[u]; i; i = edges2[i].nxt) {
        int v = edges2[i].to;
        par[v] = u; dfs(v, c);
        siz[u] += siz[v];
        if(siz[v] > siz[heavy[u]]) heavy[u] = v;
    }
}
inline void dfs2(int u, int t) {
    dfn2[u] = ++tim2;
    top[u] = t;
    ST1[tim2][0] = (Solution1){sum[u], u};
    ST2[tim2][0] = (Solution2){sum[u], u};
    if(!heavy[u]) return;
    dfs2(heavy[u], t);
    for(int i = head2[u]; i; i = edges2[i].nxt) {
        int v = edges2[i].to;
        if(heavy[u] == v) continue;
        dfs2(v, v);
    }
}
inline void clear_tree(int u) {
    for(int i = head2[u]; i; i = edges2[i].nxt) {
        int v = edges2[i].to;
        clear_tree(v);
    }
    par[u] = head2[u] = dfn2[u] = top[u] = sum[u] = siz[u] = heavy[u] = 0;
}
inline Solution1 doit1(int x, int y) {
    Solution1 ret = (Solution1){inf, -1};
    while(top[x] != top[y]) {
        ret = min(ret, query1(dfn2[top[x]], dfn2[x]));
        x = par[top[x]];
    }
    ret = min(ret, query1(dfn2[y], dfn2[x]));
    return ret;
}
inline Solution2 doit2(int x, int y) {
    Solution2 ret = (Solution2){-inf, -1};
//    printf("x=%d, y=%d\n", x, y);
    while(top[x] != top[y]) {
        if(x > 0)
//            printf("x=%d, y=%d, top[x]=%d, top[y]=%d\n", x, y, top[x], top[y]);
        ret = max(ret, query2(dfn2[top[x]], dfn2[x]));
        x = par[top[x]];
    }
    ret = max(ret, query2(dfn2[y], dfn2[x]));
    return ret;
}
int main() {
    freopen("keys.in", "r", stdin);
    freopen("keys.out", "w", stdout);
    scanf("%d %d", &n, &q);
    for(int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i <= n; ++i) scanf("%d %d", &op[i], &col[i]);
    for(int i = 1; i < n; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        addedge(u, v); addedge(v, u);
    }
    dfs0(1);
//    for(int u = 1; u <= n; ++u)
//        printf("dfn[u=%d]=%d\n", u, dfn[u]);
    for(int i = 1; i <= n; ++i) {
        nxtcol[i] = headcol[col[i]];
        headcol[col[i]] = i;
    }
    for(int c = 1; c <= n; ++c) {
        if(!headcol[c]) continue; k = 0;
        for(int i = headcol[c]; i; i = nxtcol[i]) lis[++k] = i;
        keys.clear(); money.clear();
        for(int i = headcol[c]; i; i = nxtcol[i])
            if(op[i] == 1) keys.push_back(i);
            else money.push_back(i);
        sort(&lis[1], &lis[k + 1], cmp);
        int top = 1; stk[1] = lis[1];
        for(int i = 2; i <= k; ++i) {
            int u = lis[i]; int lc = LCA(u, stk[top]);
//            printf("u=%d, stk[top]=%d, lc=%d\n", u, stk[top], lc);
            while(top > 1 && depth[stk[top - 1]] > depth[lc]) {
                addedge2(stk[top - 1], stk[top]);
                --top;
            }
            if(stk[top] == lc) stk[++top] = u;
            else if(stk[top - 1] == lc) {
                addedge2(stk[top - 1], stk[top]);
                stk[top] = u;
            } else {
                addedge2(lc, stk[top]);
                stk[top] = lc; stk[++top] = u;
            }
        }
        while(top > 1) {addedge2(stk[top - 1], stk[top]); --top;}
        tim2 = 0; dfs(stk[1], c); dfs2(stk[1], stk[1]);
        par[stk[1]] = 0;
        for(int i = tim2; i; --i)
            for(int j = 1; j <= lg[tim2 - i + 1]; ++j) {
                ST1[i][j] = min(ST1[i][j - 1], ST1[i + (1 << (j - 1))][j - 1]);
                ST2[i][j] = max(ST2[i][j - 1], ST2[i + (1 << (j - 1))][j - 1]);
            }
        for(int i = 0; i < keys.size(); ++i)
            for(int j = 0; j < money.size(); ++j) {
                int x = keys[i], y = money[j];
//                printf("x=%d, y=%d\n", x, y);
//                printf("pre: x=%d, y=%d\n", x, y);
                if(dfn[x] <= dfn[y] && dfn[y] <= out[x]) {
//                    printf("case 1\n");
                    if(sum[y] != sum[par[x]]) continue;
                    Solution1 res = doit1(y, x);
                    if(res.idx == y) {
//                        printf("case 1: x=%d, y=%d\n", x, y);
                        int z = jump(y, depth[y] - depth[x] - 1);
//                        printf("z=%d\n", z);
                        addoper(1, dfn[z] - 1, dfn[y], out[y]);
                        addoper(out[z] + 1, n, dfn[y], out[y]);
                    }
                } else if(dfn[y] <= dfn[x] && dfn[x] <= out[y]) {
//                    printf("case 2\n");
                    if(sum[x] != sum[par[y]]) continue;
//                    printf("ok0\n");
                    Solution2 res = doit2(par[x], y);
//                    printf("ok1\n");
                    res = max(res, (Solution2){sum[par[y]], par[y]});
//                    printf("ok2\n");
                    if(res.idx == par[y]) {
//                        printf("case 2: x=%d, y=%d\n", x, y);
                        int z = jump(x, depth[x] - depth[y] - 1);
                        addoper(dfn[x], out[x], 1, dfn[z] - 1);
                        addoper(dfn[x], out[x], out[z] + 1, n);
                    }
                } else {
//                    printf("case 3\n");
                    int lc = LCA(x, y);
//                    printf("lc=%d\n", lc);
                    if(sum[x] + sum[y] - sum[lc] - sum[par[lc]] != 0) continue;
//                    printf("step 1 ok\n");
                    Solution2 res2 = doit2(par[x], lc);
                    res2 = max(res2, (Solution2){sum[par[x]], par[x]});
                    if(sum[x] - res2.sum < 0) continue;
                    Solution1 res1 = doit1(y, lc);
                    if(res1.idx == y) {
//                        printf("case 3: x=%d, y=%d\n", x, y);
                        addoper(dfn[x], out[x], dfn[y], out[y]);
                    }
                }
//                printf("ok\n");
            }
        clear_tree(stk[1]); nedge2 = 0;
    }
//    for(int i = 1; i <= nopt; ++i) {
//        nxtop[i] = headop[oper[i].x];
//        headop[oper[i].x] = i;
//    }
    for(int i = 1; i <= q; ++i) {
        int x, y; scanf("%d %d", &x, &y);
        que[i].x = dfn[x]; que[i].y = dfn[y];
    }
    for(int i = 1; i <= q; ++i) {
        nxtque[i] = headque[que[i].x];
        headque[que[i].x] = i;
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = headop[i]; j; j = nxtop[j]) {
            int y = oper[j].y, d = oper[j].dir;
            modify(y, d);
        }
        for(int j = headque[i]; j; j = nxtque[j])
            final_answer[j] = quest(que[j].y);
    }
    for(int i = 1; i <= q; ++i)
        printf("%d\n", final_answer[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

已知的“错误”是调试信息有一处没有注释掉（函数 $doit2$ 里的 $if(x>0)$），但是冷静分析了一波，发现 $x>0$ 恒成立，所以并不影响结果，事实上注释掉之后也还是 $60pts$。