//为了证明我还活着还是发篇博客水水吧 QvQ

1. 题目

传送门=￣ω￣=

题意：给出一个有 $\leq 10^4$个点的带权树，有 $\leq 100$个询问，每次询问给出 $k$，表示询问是否存在距离为 $k$的点对。

2. 题解

蒟蒻の第一道点分治。

听说有大佬用 $O(n^2)$的点分治过了 QvQ（雾）

Orz 太强了！

我只会 $O(mnlog_2n)$的 QvQ（大雾）

对于每次询问，我们统计一下树中有多少对点对距离为 $k$

这很好办。每次找到重心作为树根，我们现在来计算路径经过树根且距离为 $k$的点对有多少对。

直观的想法就是把子树中所有的点到重心的距离保存到哈希表中（$hash[dep[i]]++$），然后对于每个点，去哈希表中查有几个点到重心的距离为 $k$减去该点到重心的距离，然后把查到的个数加到统计的答案中去 $tot+=hash[k-dep[i]]$。

但是我们不难发现有可能存在两个点同在重心的一个子树内，这样它们的 $lca$就不是当前重心了，它们不能统计到答案中去。所以算完整颗以重心为根的子树内路径跨越重心且距离为 $k$的点对后还要减去所有以重心的某个儿子为根的子树内路径跨越这个儿子且二者到重心的距离之和为 $k$的点对数目。

说起来有点绕口，个人认为看代码会好懂一些 QvQ

代码：

#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define NS (10005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m;

struct graph
{
    int head[NS], nxt[NS << 1], to[NS << 1], w[NS << 1], sz;
    void init() {memset(head, -1, sizeof(head)), sz = 0;}
    graph() {init();}
    void push(int a, int b, int c)
    {
        nxt[sz] = head[a], to[sz] = b, w[sz] = c, head[a] = sz++;
    }
    int operator [] (const int a) const {return to[a];}
} g;

namespace Node_Binary
{
    bool book[NS];
    int sum, sz[NS], rt, mi, Dep[NS], mp[10000005];
    stack<int> st;
    void Init() {memset(book, 0, sizeof(book)), sum = 0;}
    void SzDfs(int a, int fa)
    {
        sz[a] = 1;
        for (int i = g.head[a]; ~i; i = g.nxt[i])
            if (g[i] != fa && !book[g[i]])
                SzDfs(g[i], a), sz[a] += sz[g[i]];
    }
    void Get_Root(int a, int fa)
    {
        int mx = 0;
        for (int i = g.head[a]; ~i; i = g.nxt[i])
            if (g[i] != fa && !book[g[i]])
                Get_Root(g[i], a), mx = max(mx, sz[g[i]]);
        mx = max(mx, sum - sz[a]);
        if (mx < mi) mi = mx, rt = a;
    }
    void DepDfs(int a, int fa)
    {
        mp[Dep[a]]++, st.push(Dep[a]);
        for (int i = g.head[a]; ~i; i = g.nxt[i])
            if (g[i] != fa && !book[g[i]])
                Dep[g[i]] = Dep[a] + g.w[i], DepDfs(g[i], a);
    }
    int CalDfs(int a, int fa, int q)
    {
        int res = 0;
        if (q - Dep[a] >= 0 && q - Dep[a] <= 10000000) res = mp[q - Dep[a]];
        for (int i = g.head[a]; ~i; i = g.nxt[i])
            if (g[i] != fa && !book[g[i]])
                res += CalDfs(g[i], a, q);
        return res;
    }
    bool Binary(int a, int q)
    {
        book[a] = 1; int tot = 0;
        for (int i = g.head[a]; ~i; i = g.nxt[i])
            if (!book[g[i]])
            {
                while (!st.empty()) mp[st.top()] = 0, st.pop();
                Dep[g[i]] = g.w[i], DepDfs(g[i], 0);
                tot -= CalDfs(g[i], 0, q);
            }
        while (!st.empty()) mp[st.top()] = 0, st.pop();
        Dep[a] = 0, DepDfs(a, 0), tot += CalDfs(a, 0, q);
        if (tot > 0) return 1;
        for (int i = g.head[a]; ~i; i = g.nxt[i])
            if (!book[g[i]])
            {
                sum = sz[g[i]], mi = n, SzDfs(g[i], 0), Get_Root(g[i], 0);
                if (Binary(rt, q)) return 1;
            }
        return 0;
    }
    bool Query(int q)
    {
        Init(), mi = n, SzDfs(1, 0), Get_Root(1, 0);
        return Binary(rt, q);
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1, a, b, c; i < n; i += 1)
        IN(a), IN(b), IN(c), g.push(a, b, c), g.push(b, a, c);
    while (m--)
    {
        int q; IN(q);
        if (Node_Binary::Query(q)) puts("AYE"); else puts("NAY");
    }
    return 0;
}