1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

#include <cstdio>  
#include <algorithm>  
  
using namespace std;  
  
const int maxn = 56789;  
const int INF = 1000000007;  
  
int getint()  
{  
    int r = 0, k = 1;  
    char c;  
    for (c = getchar(); c < '0' || c > '9'; c = getchar() ) if (c == '-') k = -1;  
    for (; '0' <= c && c <= '9'; c = getchar() ) r = r * 10 - '0' + c;  
    return r * k;  
}  
  
int n, m, k;  
int h[maxn], siz[maxn];  
  
struct edge_type  
{  
    int v, next, w;  
    bool baned;  
} edge[maxn * 2]; int tote = 0;  
  
void ins(int u, int v, int w)  
{  
    edge[++tote].v = v;  
    edge[tote].next = h[u];  
    edge[tote].w = w;  
    edge[tote].baned = false;  
    h[u] = tote;  
}  
  
int fgans, fgsiz;  
  
void get_fgans(int now, int fa, int size) {  
    int tmp = 1;  
    siz[now] = 1;  
    for (int i = h[now]; i; i = edge[i].next) {  
        if (!edge[i].baned && fa != edge[i].v) {  
            get_fgans(edge[i].v, now, size);  
            siz[now] += siz[edge[i].v];  
            if (tmp < siz[edge[i].v]) tmp = siz[edge[i].v];  
        }  
    }  
    if (tmp < size - siz[now]) tmp = size - siz[now];  
    if (tmp < fgsiz) {  
        fgans = now;  
        fgsiz = tmp;  
    }  
}  
int find_gravity(int rt, int size) {  
    fgsiz = INF;  
    fgans = rt;  
    get_fgans(rt, -1, size);  
    return fgans;  
}  
  
int dis[maxn];  
int zhan[maxn], zcnt;  
  
void get_dis(int now, int nd, int fa) {  
    dis[now] = nd;  
    for (int i = h[now]; i; i = edge[i].next)  
        if (!edge[i].baned && fa != edge[i].v)  
            get_dis(edge[i].v, nd + edge[i].w, now);  
}  
  
void dfs(int now, int fa) {  
    zhan[++zcnt] = dis[now];  
    for (int i = h[now]; i; i = edge[i].next)  
        if (!edge[i].baned && fa != edge[i].v)  
            dfs(edge[i].v, now);  
}  
  
int calculate(int rt) {  
    int ret = 0;  
    zcnt = 0;  
    dfs(rt, -1);  
    sort(zhan + 1, zhan + zcnt + 1);  
    for (int i = 1, j = zcnt; i <= zcnt; ++i) {  
        for (; j && zhan[i] + zhan[j] > k; --j);  
        ret += j;  
    }  
    return ret;  
}  
  
int Ans = 0;  
  
void dfz(int now, int size)  
{  
    int rt = find_gravity(now, size);  
    get_dis(rt, 0, -1);  
    Ans += calculate(rt);  
    int v;  
    for (int i = h[rt]; i; i = edge[i].next)  
        if (!edge[i].baned) {  
            edge[i].baned = edge[((i-1)^1)+1].baned = true;  
            Ans -= calculate(edge[i].v);  
            dfz(edge[i].v, siz[edge[i].v]);  
        }  
}  
  
int main()  
{  
    n = getint();  
    m = getint();  
    int u, v, w;  
    for (int i = 1; i < n; ++i)  
    {  
        u = getint();  
        v = getint();  
        w = getint();  
        ins (u, v, w);  
        ins (v, u, w);  
    }  
    k = getint();  
    dfz(1, n);  
    printf("%d", (Ans - n >> 1));  
    return 0;  
}