2476 - Entregas do Noel

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e6 + 10;
const int OO = 0x3f3f3f3f;
const double EPS = 1e-4;

#define bug(x) cout << #x << " = " << x << '\n'
#define FOR(i, a, n) for(int i = a; i < (int)n; i++)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mt make_tuple
#define all(vetor) vetor.begin(), vetor.end()
#define X real()
#define Y imag()
//#define gc getchar_unlocked

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef complex<ll> Pll;
typedef complex<ld> Pld;

int SQ, q, n;
unordered_map<string, int> mapa;
int vertex[MAX], p[MAX], in[MAX], out[MAX], LCA[MAX], ans[MAX], rep;
int anc[MAX][20], max_log, depth[MAX], pp[MAX], node[MAX], freq[MAX], seq[2 * MAX];
vector<ii> que;
vector<int> G[MAX];
int tempo;

void dfs(int v, int p, int d)
{
    depth[v] = d;
    anc[v][0] = p;
    seq[tempo] = v;
    in[v] = tempo++;
    max_log = max(max_log, 1 + (int)log2(d));
    for(int &u : G[v])
        if(u != p)
            dfs(u, v, d + 1);
    seq[tempo] = v;
    out[v] = tempo++;
}

void build()
{
    memset(anc, -1, sizeof(anc));
    dfs(0, -1, 0);
    for(int j = 1; j <= max_log; j++)
        for(int i = 0; i < n; i++)
            if(anc[i][j-1] != -1)
                anc[i][j] = anc[anc[i][j-1]][j-1];
}

int walk(int v, int k)
{
    while(k) v = anc[v][(int)log2(k&-k)], k -= k&-k;
    return v;
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) u = walk(u, depth[u] - depth[v]);
    if(depth[u] < depth[v]) v = walk(v, depth[v] - depth[u]);
    if(u == v) return u;
    for(int i = max_log; i >= 0; i--)
        if(anc[u][i] != anc[v][i])
            u = anc[u][i], v = anc[v][i];
    return anc[u][0];
}

bool cmp(int a, int b)
{
    if(que[a].fi / SQ == que[b].fi / SQ)
    {
        if((que[a].fi / SQ) & 1)
            return que[a].se > que[b].se;
        else
            return que[a].se < que[b].se;
    }
    else
        return que[a].fi < que[b].fi;
}

inline void mo(int i)
{
    int v = seq[i];
    if(node[v] and --freq[vertex[v]] == 0) rep--;
    if(!node[v] and ++freq[vertex[v]] == 1) rep++;
    node[v] ^= 1;
}

int main()
{
    scanf(" %d %d", &n, &q);
    char brinquedo[100];
    string aux;
    int id = 1;
    REP(i, n)
    {
        scanf("%s", brinquedo);
        aux = brinquedo;
        auto it = mapa.find(aux);
        if(it == mapa.end())
        {
            vertex[i] = id;
            mapa[aux] = id++;
        }
        else
            vertex[i] = it->se;
    }
    int u, v;
    REP(i, n-1)
    {
        scanf("%d %d", &u, &v); u--; v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    build();
    REP(i, q)
    {
        scanf("%d %d", &u, &v); u--; v--;
        int l, r;
        LCA[i] = lca(u, v);
        if(in[u] > in[v])
            swap(u, v);
        if(u == LCA[i])
            que.pb({in[LCA[i]], in[v]});
        else
            que.pb({out[u], in[v]});
        pp[i] = i;
    }
    SQ = sqrt(n);
    sort(pp, pp + q, cmp);

    int L = 0, R = 0;
    REP(i, q)
    {
        int l = que[pp[i]].fi, r = que[pp[i]].se, LC = LCA[pp[i]];
        while(L < l) mo(L++);
        while(L > l) mo(--L);
        while(R < r + 1) mo(R++);
        while(R > r + 1) mo(--R);
        if(LC != seq[l])
            mo(in[LC]);
        ans[pp[i]] = rep;
        if(LC != seq[l])
            mo(in[LC]);
    }
    REP(i, q)
        printf("%d\n", ans[i]);

    return 0;
}