#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;
}
点分治
Share