代码如下:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int vis[40005];
int n,m;
int g,h,ph;
int sizeroot;
int size[40005],weigh[40005];
int cnt[40005],ans[90005],dis[90005];
int k[40006];
int root;
struct Node{
int to,val;
Node(int to,int val) :to(to),val(val){}
};
vector <Node > e[40005];
inline int read(){
register int x=0,w=0; char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return w?-x:x;
}
inline void add(int u,int v,int l){
e[u].push_back(Node(v,l));
e[v].push_back(Node(u,l));
}
inline void getcentral(int now,int fa){
size[now]=1,weigh[now]=0;
for(register int i=0;i<e[now].size();++i){
int to=e[now][i].to;
if(to==fa||vis[to]) continue;
getcentral(to,now);
size[now]+=size[to];
weigh[now]=max(weigh[now],size[to]);
}
weigh[now]=max(weigh[now],sizeroot-size[now]);
if(weigh[root]>weigh[now]) root=now;
}
inline void clean_cnt(int now,int fa,int len){
if(len<=10000000) cnt[len]=0;
for(register int i=0;i<e[now].size();++i){
int to=e[now][i].to;
if(to==fa||vis[to]) continue;
clean_cnt(to,now,len+e[now][i].val);
}
}
inline void change_cnt(int now,int fa,int len){
if(len<=10000000) cnt[len]++;
for(register int i=0;i<e[now].size();++i){
int to=e[now][i].to;
if(to==fa||vis[to]) continue;
change_cnt(to,now,len+e[now][i].val);
}
}
inline void change_ans(int now,int fa,int len){
for(register int i=1;i<=m;++i){
if(len<=k[i]){
ans[i]+=cnt[k[i]-len];
}
}
for(register int i=0;i<e[now].size();++i){
int to=e[now][i].to;
if(to==fa||vis[to]) continue;
change_ans(to,now,len+e[now][i].val);
}
}
inline void divide(int now){
vis[now]=1;
cnt[0]=1;
for(register int i=0;i<e[now].size();++i){
int to=e[now][i].to;
if(vis[to]) continue;
change_ans(to,now,e[now][i].val);
change_cnt(to,now,e[now][i].val);
}
clean_cnt(now,0,0);
for(register int i=0;i<e[now].size();++i){
int to=e[now][i].to;
if(vis[to]) continue;
root=0,weigh[0]=0x3f3f3f;
sizeroot=size[to];
getcentral(to,now);
divide(root);
}
}
int tot;
signed main(){
n=read();
for(register int i=1;i<=n-1;++i){
g=read(),h=read(),ph=read();
add(g,h,ph);
}
g=read();
m=g+1;
for(register int i=0;i<=g;++i){
k[++tot]=i;
}
int cnt=0;
sizeroot=n,root=0,weigh[root]=0x3f3f3f;
getcentral(1,0);
divide(root);
for(register int i=1;i<=m;++i){
cnt+=ans[i];
}
cout<<cnt;
return 0;
}