点分治TLE+RE30求助

#include <bits/stdc++.h>
using namespace std;
// using LL = long long;
const int MAXN = 200005;
struct edge {
  int v, w;
};
int n, k, ans = 1e9;
int root, bigChildSize;
int size[MAXN];
int L, p;
int q1[MAXN], q2[MAXN], cnt[1000006];
bool vis[MAXN];
vector<edge> g[MAXN];
void getCentroid(int u, int fa) {
  size[u] = 1;
  int bigSize = 0;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].v, w = g[u][i].w;
    if (v == fa || vis[v])
      continue;
    getCentroid(v, u);
    size[u] += size[v];
    if (size[v] > bigSize)
      bigSize = size[v];
  }
  if (n - size[u] > bigSize)
    bigSize = n - size[u];
  if (bigSize < bigChildSize) {
    bigChildSize = bigSize;
    root = u;
  }
}
void getDis(int u, int fa, int dis, int bs) {
  q1[++p] = dis;
  q2[p] = bs;
  size[u] = 1;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i].v, w = g[u][i].w;
    if (v == fa || vis[v])
      continue;
    getDis(v, u, dis + w, bs + 1);
    size[u] += size[v];
  }
}
void solve(int u, int fa, int nodeCnt) {
  root = u;
  bigChildSize = nodeCnt - 1;
  getCentroid(u, fa);
  p = L = 1;
  q1[1] = 0;
  cnt[0] = 0;
  vis[root] = true;
  // 树上背包
  for (int i = 0; i < g[root].size(); i++) {
    int v = g[root][i].v, w = g[root][i].w;
    if (v == fa || vis[v])
      continue;
    getDis(v, root, w, 1);
    for (int j = L + 1; j <= p; j++) {
      if (k - q1[j] >= 0) {
        for (int m = k - q1[j]; m >= 0; m--)
          ans = min(ans, cnt[k - q1[j]] + q2[j]);
      }
    }
    for (int j = L + 1; j <= p; j++)
      cnt[q1[j]] = min(cnt[q1[j]], q2[j]);
    L = p;
  }
  // 还原 cnt 数组
  for (int i = 1; i <= p; i++)
    cnt[q1[i]] = 1e9;
  // 分治，处理子问题
  int tr = root;
  for (int i = 0; i < g[tr].size(); i++) {
    int v = g[tr][i].v, w = g[tr][i].w;
    if (v == fa || vis[v])
      continue;
    solve(v, tr, size[v]);
  }
}

inline int read(){
	char ch=getchar();int x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}

int main() {
  memset(cnt, 0x3f, sizeof cnt);
  n=read();
  k=read();
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    u=read(); v=read(); w=read();
    u++;
    v++;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  solve(1, 0, n);
  printf("%d\n", ((ans >= n) ? -1 : ans));
  return 0;
}