萌新求助点分治

RT，9 个点全部 WA。

照着这篇日报写的。

/*
========= Plozia =========
    Author:Plozia
    Problem:P3806 【模板】点分治1
    Date:2021/5/6
========= Plozia =========
*/

#include <bits/stdc++.h>

typedef long long LL;
const int MAXN = 1e4 + 10;
int n, m, Head[MAXN], cnt_Edge = 1, q[MAXN], root = 1, res[MAXN], f[MAXN], Size[MAXN], cnt, d[MAXN], total_node;
struct node { int to, val, Next; } Edge[MAXN << 1];
bool book[MAXN];

int read()
{
    int sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
    return sum * fh;
}
void add_Edge(int x, int y, int z) { ++cnt_Edge; Edge[cnt_Edge] = (node){y, z, Head[x]}; Head[x] = cnt_Edge; }
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }

void Get_zx(int now, int father)
{
    f[now] = 0, Size[now] = 1;
    for (int i = Head[now]; i; i = Edge[i].Next)
    {
        int u = Edge[i].to;
        if (book[u] || u == father) continue ;
        Get_zx(u, now);
        f[now] = Max(f[now], Size[u]);
        Size[now] += Size[u];
    }
    f[now] = Max(f[now], total_node - f[now]);
    if (f[now] < f[root]) root = now;
}

void Get_dis(int now, int father, int dis)
{
    for (int i = Head[now]; i; i = Edge[i].Next)
    {
        int u = Edge[i].to;
        if (book[u] || u == father) continue ;
        ++cnt; d[cnt] = dis + Edge[i].val;
        Get_dis(u, now, d[cnt]);
    }
}

void Get_ans(int now, int dis, int Tag)
{
    cnt = 1; d[cnt] = dis;
    Get_dis(now, 0, dis);
    std::sort(d + 1, d + cnt + 1);
    for (int _ = 1; _ <= m; ++_)
    {
        int l = 1, r = cnt, ans = 0;
        while (l < r && d[l] + d[r] < q[_]) ++l;
        while (l < r)
        {
            ans += std::upper_bound(d + l, d + cnt + 1, q[_]) - std::lower_bound(d + l, d + cnt + 1, q[_]);
            ++l;
        }
        if (Tag == 0) res[_] += ans;
        else res[_] -= ans;
    }
}

void Solve(int now)
{
    book[now] = 1; Get_ans(now, 0, 0);
    for (int i = Head[now]; i; i = Edge[i].Next)
    {
        int u = Edge[i].to;
        if (book[u]) continue ;
        Get_ans(u, Edge[i].val, 1);
        total_node = Size[u]; root = 0;
        Get_zx(u, 0); Solve(root);
    }
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i < n; ++i)
    {
        int x = read(), y = read(), z = read();
        add_Edge(x, y, z); add_Edge(y, x, z);
    }
    for (int i = 1; i <= m; ++i) q[i] = read();
    Get_zx(1, 0); Solve(root);
    for (int i = 1; i <= m; ++i)
        if (res[i]) printf("AYE\n");
        else printf("NAY\n");
    return 0;
}