你说的对，但是启发式合并哈希表真的既不需要脑子也不需要数据结构。

btd

我印象中好像都是 gp_hash_table 比 unordered_map 快的。

但这题中 unordered_map 要开 O2 才过，gp_hash_table 开不开 O2 都 TLE on #20，而且明显慢于前者。

求问：

1. 为什么这里 gp_hash_table 比 unordered_map 慢？
2. 空哈希表占多大内存？
3. 哈希表的空间和 size 什么关系？
4. unordered_map 和 gp_hash_table 应该怎么选择？

//unordered_map
#include <cstdio>
#include <vector>
#include <unordered_map>
using namespace std;
struct E
{
    int v, t;
} e[600050];
vector<int> t[300050], g[300050];
unordered_map<int, int> *x[300050], *y[300050];
int n, m, c, w[300050], q[300050], d[300050], s[300050],
    U[300050], V[300050], L[300050], h[300050], f[300050][20];
void A(int u, int v)
{
    e[++c] = {v, h[u]};
    h[u] = c;
}
void D(int u)
{
    for (int i = h[u], v; i; i = e[i].t)
        if (!d[v = e[i].v])
        {
            d[v] = d[f[v][0] = u] + 1;
            for (int j = 1; f[v][j - 1]; ++j)
                f[v][j] = f[f[v][j - 1]][j - 1];
            D(v);
        }
}
void Q(int u, int k)
{
    (*x[u])[d[u]] += s[u];
    for (auto i : t[u])
        ++(*y[u])[i];
    for (int i = h[u], v; i; i = e[i].t)
        if ((v = e[i].v) != k)
        {
            Q(v, u);
            if (x[u]->size() < x[v]->size())
                swap(x[u], x[v]);
            for (auto j : *x[v])
                (*x[u])[j.first] += j.second;
            x[v]->clear();
            if (y[u]->size() < y[v]->size())
                swap(y[u], y[v]);
            for (auto j : *y[v])
                (*y[u])[j.first] += j.second;
            y[v]->clear();
        }
    q[u] = (*x[u])[w[u] + d[u]] + (*y[u])[w[u] - d[u]];
    for (auto i : g[u])
        --(*x[u])[d[U[i]]],
            --(*y[u])[d[U[i]] - (d[L[i]] << 1)],
            q[u] -= d[U[i]] - d[L[i]] == w[L[i]];
}
int l(int x, int y)
{
    if (d[x] < d[y])
        swap(x, y);
    while (d[x] > d[y])
        x = f[x][__lg(d[x] - d[y])];
    if (x == y)
        return x;
    for (int k = __lg(n); k >= 0; --k)
        if (f[x][k] != f[y][k])
            x = f[x][k], y = f[y][k];
    return f[x][0];
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i < n; ++i)
        scanf("%d%d", &u, &v), A(u, v), A(v, u);
    D(d[1] = 1);
    for (int i = 1; i <= n; ++i)
        scanf("%d", w + i),
            x[i] = new unordered_map<int, int>,
            y[i] = new unordered_map<int, int>;
    for (int i = 0; i < m; ++i)
        scanf("%d%d", U + i, V + i), ++s[U[i]],
            g[L[i] = l(U[i], V[i])].push_back(i),
            t[V[i]].push_back(d[U[i]] - (d[L[i]] << 1));
    Q(1, 0);
    for (int i = 1; i <= n; ++i)
        printf("%d ", q[i]);
    return 0;
}

//gp_hash_table
#include <cstdio>
#include <vector>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
struct E
{
    int v, t;
} e[600050];
vector<int> t[300050], g[300050];
gp_hash_table<int, int> *x[300050], *y[300050];
int n, m, c, w[300050], q[300050], d[300050], s[300050],
    U[300050], V[300050], L[300050], h[300050], f[300050][20];
void A(int u, int v)
{
    e[++c] = {v, h[u]};
    h[u] = c;
}
void D(int u)
{
    for (int i = h[u], v; i; i = e[i].t)
        if (!d[v = e[i].v])
        {
            d[v] = d[f[v][0] = u] + 1;
            for (int j = 1; f[v][j - 1]; ++j)
                f[v][j] = f[f[v][j - 1]][j - 1];
            D(v);
        }
}
void Q(int u, int k)
{
    (*x[u])[d[u]] += s[u];
    for (auto i : t[u])
        ++(*y[u])[i];
    for (int i = h[u], v; i; i = e[i].t)
        if ((v = e[i].v) != k)
        {
            Q(v, u);
            if (x[u]->size() < x[v]->size())
                swap(x[u], x[v]);
            for (auto j : *x[v])
                (*x[u])[j.first] += j.second;
            x[v]->clear();
            if (y[u]->size() < y[v]->size())
                swap(y[u], y[v]);
            for (auto j : *y[v])
                (*y[u])[j.first] += j.second;
            y[v]->clear();
        }
    q[u] = (*x[u])[w[u] + d[u]] + (*y[u])[w[u] - d[u]];
    for (auto i : g[u])
        --(*x[u])[d[U[i]]],
            --(*y[u])[d[U[i]] - (d[L[i]] << 1)],
            q[u] -= d[U[i]] - d[L[i]] == w[L[i]];
}
int l(int x, int y)
{
    if (d[x] < d[y])
        swap(x, y);
    while (d[x] > d[y])
        x = f[x][__lg(d[x] - d[y])];
    if (x == y)
        return x;
    for (int k = __lg(n); k >= 0; --k)
        if (f[x][k] != f[y][k])
            x = f[x][k], y = f[y][k];
    return f[x][0];
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i < n; ++i)
        scanf("%d%d", &u, &v), A(u, v), A(v, u);
    D(d[1] = 1);
    for (int i = 1; i <= n; ++i)
        scanf("%d", w + i),
            x[i] = new gp_hash_table<int, int>,
            y[i] = new gp_hash_table<int, int>;
    for (int i = 0; i < m; ++i)
        scanf("%d%d", U + i, V + i), ++s[U[i]],
            g[L[i] = l(U[i], V[i])].push_back(i),
            t[V[i]].push_back(d[U[i]] - (d[L[i]] << 1));
    Q(1, 0);
    for (int i = 1; i <= n; ++i)
        printf("%d ", q[i]);
    return 0;
}