求助，点分治后3个点TLE

已经离线处理了，还是死活过去不。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define LL long long

using namespace std;

const int kN = 1e4 + 5, kM = 1e7 + 5, kInf = 2e9;

struct Edge {
  int x, to, w;
}edges[2 * kN];

int n, m;
int tot, q[kN], siz[kN], rt, ms[kN], dis[kN], sum, maxs, a[kN], cnt, g[kN], Lim;
bool ans[kN], v[kN];
vector<int> G[kN];

void Rd(int &x) {
  int y = 1; char c = getchar();
  x = 0;
  while (c < '0' || c > '9') {if (c == '-') y = -1; c = getchar();}
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  x *= y;
} 

void Add_edge(int u, int v, int w) {
  edges[++tot] = (Edge) {u, v, w};
  G[u].push_back(tot);
  edges[++tot] = (Edge) {v, u, w};
  G[v].push_back(tot);
}

void Find_rt(int x, int fa) {
  siz[x] = 1, ms[x] = 0;
  for (int i = 0; i < G[x].size(); ++i) {
    Edge &e = edges[G[x][i]];
    if (e.to == fa || v[e.to]) continue;
    Find_rt(e.to, x);
    siz[x] += siz[e.to];
    ms[x] = max(ms[x], siz[e.to]);
  }
  ms[x] = max(ms[x], sum - siz[x]);
  if (ms[x] > maxs) {
    maxs = ms[x];
    rt = x;
  }
}

void Get_dis(int x, int fa, int top) {
  g[x] = top, siz[x] = 1;
  if (dis[x] > Lim) return;
  for (int i = 0; i < G[x].size(); ++i) {
    Edge &e = edges[G[x][i]];
    if (e.to == fa || v[e.to]) continue;
    dis[e.to] = dis[x] + e.w;
    Get_dis(e.to, x, top);
    siz[x] += siz[e.to];
  }
  a[++cnt] = x;
}

bool cmp(int x, int y) {
  return dis[x] < dis[y];
}

void Calc(int x) {
  a[cnt = 1] = x, g[x] = dis[x] = 0;
  for (int i = 0; i < G[x].size(); ++i) {
    Edge &e = edges[G[x][i]];
    if (v[e.to]) continue;
    dis[e.to] = e.w;
    Get_dis(e.to, x, e.to);
  }
  sort(a + 1, a + 1 + cnt, cmp);
  for (int i = 1; i <= m; ++i) {
    if (ans[i]) continue;
    int l = 1, r = cnt;
    while (l < r) {
      if (dis[a[l]] + dis[a[r]] > q[i]) r--;
      else if (dis[a[l]] + dis[a[r]] < q[i]) l++;
      else if (dis[a[l]] + dis[a[r]] == q[i]) {
        if (g[a[l]] ^ g[a[r]]) {
          ans[i] = 1; break;
        }
        else {
          if (dis[a[r]] != dis[a[r - 1]]) l++;
          else r--;
        }
      }
    }
  }
}

void Solve(int x) {
  v[x] = 1, Calc(x);
  for (int i = 0; i < G[x].size(); ++i) {
    Edge &e = edges[G[x][i]];
    if (v[e.to]) continue;
    sum = siz[e.to], maxs = 0, ms[rt = 0] = kInf;
    Find_rt(e.to, 0); Solve(rt);
  }
}

int main() {
  Rd(n); Rd(m);
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    Rd(u); Rd(v); Rd(w);
    Add_edge(u, v, w);
  }
  for (int i = 1; i <= m; ++i) Rd(q[i]), Lim = max(Lim, q[i]);
  sum = n, ms[0] = kInf;
  Find_rt(1, 0);
  Solve(rt);
  for (int i = 1; i <= m; ++i) {
    if (ans[i]) printf("AYE\n");
    else printf("NAY\n");
  }
  return 0;
}