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
| #include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = N << 1;
int n, m;
int idx;
int h[N], e[M], ne[M], w[M];
bool st[N];
int p[N], q[N];
void add(int x, int y, int z)
{
idx ++;
e[idx] = y, ne[idx] = h[x], h[x] = idx, w[idx] = z;
}
int get_size(int x, int father)
{
if(st[x]) return 0;
int res = 1;
for(int i = h[x]; ~i;i = ne[i])
if(e[i] != father)
res += get_size(e[i], x);
return res;
}
int get_wc(int x, int father, int tot, int& wc)
{
if(st[x]) return 0;
int sum = 1, ms = 0;
for(int i = h[x]; ~i;i = ne[i])
{
int j = e[i];
if(j == father) continue;
int t = get_wc(j, x, tot, wc);
ms = max(ms, t);
sum += t;
}
ms = max(ms, tot - sum);
if(ms <= tot / 2) wc = x;
return sum;
}
void get_dist(int x, int father, int dist, int& qt)
{
if(st[x]) return ;
q[++ qt] = dist;
for(int i = h[x]; ~i;i = ne[i])
if(e[i] != father)
get_dist(e[i], x, dist + w[i], qt);
}
int get(int a[], int k)
{
sort(a + 1, a + k + 1);
int res = 0;
for(int i = k, j = 0;i >= 1;i --)
{
while(j + 1 < i && a[j + 1] + a[i] <= m) j ++;
j = min(i - 1, j);
res += j;
}
return res;
}
int calc(int x)
{
if(st[x]) return 0;
int res = 0;
get_wc(x, -1, get_size(x, -1), x);
st[x] = 1;
int pt = 0;
for(int i = h[x]; ~i;i = ne[i])
{
int j = e[i], qt = 0;
get_dist(j, -1, w[i], qt);
res -= get(q, qt);
for(int k = 1;k <= qt;k ++)
{
if(q[k] <= m) res ++;
p[++ pt] = q[k];
}
}
res += get(p, pt);
for(int i = h[x]; ~i;i = ne[i])
res += calc(e[i]);
return res;
}
int main()
{
while(scanf("%d%d", &n, &m), n || m)
{
idx = 0;
memset(st, 0, sizeof(st));
memset(h, -1, sizeof(h));
for(int i = 1;i < n;i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
printf("%d\n", calc(0));
}
return 0;
}
|