点分治

具体待更
代码：
  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 #define re register
  6 #define rep(i, a, b) for (re int i = a; i <= b; ++i)
  7 #define repd(i, a, b) for (re int i = a; i >= b; --i)
  8 #define For(i, a, b, s) for (re int i = a; i <= b; s)
  9 #define maxx(a, b) a = max(a, b)
 10 #define minn(a, b) a = min(a, b)
 11 #define LL long long
 12 #define INF (1 << 30)
 13 
 14 inline int read() {
 15     int w = 0, f = 1; char c = getchar();
 16     while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
 17     while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
 18     return w * f;
 19 }
 20 
 21 const int maxn = 1e4 + 5, maxm = 100 + 5;
 22 
 23 struct Edge {
 24     int u, v, w, pre;
 25 } e[maxn << 1];
 26 int ec, G[maxn];
 27 void init() { memset(G, -1, sizeof(G)); ec = 0; }
 28 void add(int u, int v, int w) { e[ec++] = (Edge){u, v, w, G[u]}; G[u] = ec-1; }
 29 #define iter(i, u) for (register int i = G[u]; i != -1; i = e[i].pre)
 30 
 31 struct Pair {
 32     int d, id;
 33     bool operator < (const Pair &r) const { return d < r.d; }
 34 } p[maxn];
 35 int N, M;
 36 int ask[maxm], ans[maxm];
 37 int son[maxn], rt, maxp[maxn], vis[maxn], cnt;
 38 
 39 void get_dist(int u, int fa, int rt, int dist) {
 40     son[u] = 1; p[cnt++] = (Pair){dist, rt};
 41     iter(i, u)
 42         if (e[i].v != fa && !vis[e[i].v]) {
 43             get_dist(e[i].v, u, rt, dist + e[i].w);
 44             son[u] += son[e[i].v];
 45         }
 46 }
 47 
 48 int query(int v) {
 49     int l = 0, r = cnt-1, res = cnt;
 50     while (l <= r) {
 51         int mid = (l + r) >> 1;
 52         if (v >= p[mid].d) l = mid+1, res = mid;
 53         else r = mid-1;
 54     }
 55     return res;
 56 }
 57 
 58 void solve(int u) {
 59     cnt = 1;
 60     iter(i, u) {
 61         if (vis[e[i].v]) continue;
 62         get_dist(e[i].v, u, e[i].v, e[i].w);
 63     }
 64     sort(p, p+cnt);
 65     rep(i, 1, M) if (!ans[i])
 66         rep(s, 0, cnt) {
 67             int t = query(ask[i]-p[s].d);
 68             while (p[s].id == p[t].id && p[t].d == p[t+1].d) t++;
 69             if (s == t || p[s].id == p[t].id) continue;
 70             if (p[s].d + p[t].d == ask[i]) {
 71                 ans[i] = 1; break;
 72             }
 73         }
 74 }
 75 
 76 int get_rt(int u, int fa, int sum) {
 77     maxp[u] = 0; int son = 1;
 78     iter(i, u)
 79         if (e[i].v != fa && !vis[e[i].v]) {
 80             int child = get_rt(e[i].v, u, sum);
 81             maxx(maxp[u], child);
 82             son += child;
 83         }
 84     maxx(maxp[u], sum - son);
 85     if (maxp[u] < maxp[rt]) rt = u;
 86     return son;
 87 }
 88 
 89 void divid(int u) {
 90     solve(u); vis[u] = 1;
 91     iter(i, u)
 92         if (!vis[e[i].v]) {
 93             rt = 0;
 94             get_rt(e[i].v, e[i].v, son[e[i].v]);
 95             divid(rt);
 96         }
 97 }
 98 
 99 int main() {
100     init(); maxp[rt = 0] = INF;
101     N = read(), M = read();
102     rep(i, 1, N-1) {
103         int u = read(), v = read(), w = read();
104         add(u, v, w); add(v, u, w);
105     }
106     rep(i, 1, M) ask[i] = read();
107     rt = 0; get_rt(1, 1, N); divid(rt);
108     rep(i, 1, M) printf("%s
", ans[i] ? "AYE" : "NAY");
109     return 0;
110 }