点分治板题是不需要判 1e7 和复杂的清空桶的。

btd

求问清空 unordered_set 的复杂度，看起来是 O(\text{元素个数的})。

而且用 unordered_set 写这个题比较方便，直接 clear 就能清空了，也不用判 1e7。

#include <cstdio>
#include <unordered_set>
using namespace std;
struct E
{
    int v, w, t;
} e[20050];
unordered_set<int> D, C;
int n, m, c, R, q[150], d[10050], s[10050], p[10050], h[10050];
bool r[150], b[10050];
void A(int u, int v, int w)
{
    e[++c] = {v, w, h[u]};
    h[u] = c;
}
void X(int u, int k, int t)
{
    s[u] = 1;
    p[u] = 0;
    for (int i = h[u], v; i; i = e[i].t)
        if (!b[v = e[i].v] && v != k)
            X(v, u, t), s[u] += s[v], p[u] = max(p[u], s[v]);
    if (p[R] > (p[u] = max(p[u], t - s[u])))
        R = u;
}
void Y(int u, int k)
{
    D.insert(d[u]);
    for (int i = h[u], v; i; i = e[i].t)
        if (!b[v = e[i].v] && v != k)
            d[v] = d[u] + e[i].w, Y(v, u);
}
void Q(int u, int k)
{
    b[u] = 1;
    C.insert(0);
    for (int i = h[u], v; i; i = e[i].t)
        if (!b[v = e[i].v] && v != k)
        {
            d[v] = e[i].w;
            Y(v, u);
            for (auto j : D)
                for (int k = 0; k < m; ++k)
                    if (q[k] >= j)
                        r[k] |= C.contains(q[k] - j);
            for (auto j : D)
                C.insert(j);
            D.clear();
        }
    C.clear();
    for (int i = h[u], v; i; i = e[i].t)
        if (!b[v = e[i].v] && v != k)
            p[R = 0] = 1e9, X(v, u, s[v]), X(R, 0, s[v]), Q(R, u);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i < n; ++i)
        scanf("%d%d%d", &u, &v, &w), A(u, v, w), A(v, u, w);
    for (int i = 0; i < m; ++i)
        scanf("%d", q + i);
    p[0] = 1e9;
    X(1, 0, n);
    X(R, 0, n);
    Q(R, 0);
    for (int i = 0; i < m; ++i)
        puts(r[i] ? "AYE" : "NAY");
    return 0;
}