点分治

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>

struct Edge {
  Edge(int to, int cost, Edge *next) : to(to), cost(cost), next(next) {  }
  int to;
  int cost;
  Edge *next;
};

Edge *first[40005];
int noden;
int size[40005];
bool vis[40005];
int limit;
int ans;

void addEdge(int from, int to, int cost) {
  first[from] = new Edge(to, cost, first[from]);
}

void getSize(int now, int fa, std::queue<int> &visit) {
  size[now] = 1;
  visit.push(now);
  for(Edge *edg = first[now]; edg != NULL; edg = edg->next) {
    if(vis[edg->to]) continue;
    if(edg->to == fa) continue;
    getSize(edg->to, now, visit);
    size[now] += size[edg->to];
  }
  return;
}
int getRoot(int start) {
  std::queue<int> visit;
  getSize(start, -1, visit);
  int totSize = size[start];
  int max = 0;
  while(!visit.empty()) {
    int now = visit.front();
    visit.pop();
    size[now] = std::max(size[now], totSize - size[now]);
    if(size[now] > size[max]) max = now;
  }
  return max;
}

void makeDepth(int now, int fa, int depth, std::vector<int> &res) {
  res.push_back(depth);
  for(Edge *edg = first[now]; edg != NULL; edg = edg->next) {
    if(vis[edg->to]) continue;
    if(edg->to == fa) continue;
    makeDepth(edg->to, now, depth + edg->cost, res);
  }
}
int cacl(int root, int edge) {
  std::vector<int> depth;
  makeDepth(root, -1, 0, depth);
  std::sort(depth.begin(), depth.end());

  int res = 0;
  for(int l = 0, r = depth.size() - 1; l < depth.size() && r >= 0 && depth[l] <= limit && l < r; ++l) {
    while(r >= 0 && depth[l] + depth[r] + (edge << 1) > limit) --r;
    if(l >= r) break;
    res += r - l;
  }
  return res;
}

void solve(int now) {
  ans += cacl(now, 0);
  vis[now] = true;
  for(Edge *edg = first[now]; edg != NULL; edg = edg->next) {
    if(vis[edg->to]) continue;
    ans -= cacl(edg->to, edg->cost);
    solve(getRoot(edg->to));
  }
  return;
}

int main() {
  scanf("%d", &noden);
  for(int i = 1; i < noden; ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    addEdge(a, b, c);
    addEdge(b, a, c);
  }
  scanf("%d", &limit);
  solve(getRoot(1));
  printf("%d\n", ans);
  return 0;
}