1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 using namespace std;  6   7 typedef long long ll;  8 const ll maxn = 100010;  9 const ll INF = 0x3f3f3f3f; 10  11 struct node { 12     ll data, weight, size;  13     node *son[2], *fa; 14 }e[maxn]; ll ne = 0; 15 node* root; 16  17 void update(node* x) { 18     x-> size = x-> weight; 19     for(ll i = 0; i < 2; ++ i) { 20         if(x-> son[i]) x-> size += x-> son[i]-> size; 21     } 22 } 23  24 void rotate(node *x, ll f) { 25     node* t = x-> fa; 26     if(t-> fa) { 27         if(t-> fa-> son[0] == t) t-> fa-> son[0] = x; 28         else t-> fa-> son[1] = t; 29     } 30     x-> fa = t-> fa, x-> size = t-> size, t-> fa = x; 31     t-> son[f] = x-> son[!f]; 32     if(x-> son[!f]) x-> son[!f]-> fa = t; 33     x-> son[!f] = t; 34     update(t); 35 } 36  37 void splay(node* x, node* f) { 38     while(x-> fa != f) { 39         if(x-> fa-> fa == f) { 40         ll a = x-> fa-> son[0] == x ? 0 : 1; 41         rotate(x, a); 42         } 43         else { 44             node* t = x-> fa, *r = t-> fa; 45             ll a = r-> son[0] == t ? 0 : 1; 46             ll b = t-> son[0] == x ? 0 : 1; 47             if(a == b) rotate(t, a), rotate(x, b); 48             else rotate(x, b), rotate(x, a); 49         } 50     } 51     if(x-> fa == NULL) root = x; 52 } 53  54 node* newnode(ll v) { 55     node* x = e + ne ++; 56     x-> data = http://www.mamicode.com/v, x-> size = x-> weight = 1; 57     x-> son[0] = x-> son[1] = NULL; 58     return x; 59 } 60  61 void insert(ll v) { 62     node* x = root; 63     while(x) { 64         x-> size ++; 65         if(x-> data =http://www.mamicode.com/= v) { 66             x-> weight ++; 67             splay(x, NULL); break; 68         } 69         else { 70             ll a = x-> data > v ? 0 : 1; 71             if(x-> son[a]) x = x-> son[a]; 72             else { 73                 x-> son[a] = newnode(v); 74                 x-> son[a]-> fa = x; 75                 splay(x-> son[a], NULL); 76                 break; 77             } 78         } 79     } 80     if(!x) root = newnode(v), root-> fa = NULL; 81 } 82  83 ll work(ll v) { 84     node *x = root; ll ret = 0; 85     while(x) { 86         if(x-> data <= v) { 87             ret += x-> weight + (x-> son[0] ? x-> son[0]-> size : 0); 88             x = x-> son[1]; 89         } 90         else x = x-> son[0]; 91     } 92     return ret; 93 } 94  95 struct edge { 96     ll t, d; 97     edge* next; 98 }se[maxn * 2], *head[maxn]; ll oe = 0; 99 ll n, m, a[maxn], top = 0;100 ll s[maxn], stop = 0;101 102 void addedge(ll f, ll t, ll d) {103     se[oe].t = t, se[oe].d = d, se[oe].next = head[f], head[f] = se + oe ++;104 }105 106 bool vis[maxn]; ll size[maxn], dis[maxn];107 108 void dfs(ll x, ll fa) {109     size[x] = 1; s[++ stop] = x;110     for(edge* p = head[x]; p; p = p-> next) if(p-> t != fa && !vis[p-> t]) dfs(p-> t, x), size[x] += size[p-> t];111 }112 113 void find_dis(ll x, ll fa) {114     a[++ top] = x;115     for(edge* p = head[x]; p; p = p-> next) {116         if(!vis[p-> t] && p-> t != fa) dis[p-> t] = dis[x] + p-> d, find_dis(p-> t, x);117     }118 }119 120 ll int_get() {121     ll x = 0; char c = (char)getchar(); bool f = 0;122     while(!isdigit(c) && c != ‘-‘) c = (char)getchar();123     if(c == ‘-‘) c = (char)getchar(), f = 1;124     while(isdigit(c)) {125         x = x * 10 + (int)(c - ‘0‘);126         c = (char)getchar();127     }128     if(f) x = -x;129     return x;130 }131 132 void read() {133     n = int_get();134     for(ll i = 1; i <= n - 1; ++ i) {135         ll u, v, w; u = int_get(), v = int_get(), w = int_get();136         addedge(u, v, w), addedge(v, u, w);137     }138     m = int_get();139 }140 141 ll ans = 0;142 143 void sov(ll x) {144     stop = 0;145     dfs(x, 0); ll tot = size[x];146     if(tot == 1) return; 147     ll Max = INF, pos = x; 148     for(ll j = 1; j <= stop; ++ j) {149         ll i = s[j];150         ll tmax = 0;151         for(edge* p = head[i]; p; p = p-> next) if(!vis[p-> t] && size[x] > size[p-> t]) tmax = max(tmax, size[p-> t]);152         tmax = max(tot - size[i], tmax);153         if(Max > tmax) Max = tmax, pos = i;154     }155     ll rt = pos; root = NULL; ne = 0;156     insert(0);157     for(edge* p = head[rt]; p; p = p-> next) {158         if(!vis[p-> t]) {159             top = 0, dis[p-> t] = p-> d, find_dis(p-> t, rt);160             for(ll i = 1; i <= top; ++ i) ans += work(m - dis[a[i]]);161             for(ll i = 1; i <= top; ++ i) insert(dis[a[i]]);162         }163     }164     vis[rt] = 1;165     for(edge* p = head[rt]; p; p = p-> next) {166         if(!vis[p-> t]) sov(p-> t);167     }168 }169 170 int main() {171     freopen("test.in", "r", stdin);172     freopen("test.out", "w", stdout);173     read(); 174     memset(vis, 0, sizeof(vis));175     sov(1);176     printf("%lld\n", ans);177     return 0;178 }