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
| #include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
namespace IO
{
const int BUFSIZE = 1 << 20;
char ibuf[BUFSIZE], *is = ibuf, *it = ibuf;
inline char getchar() { if (is == it) it = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); return *is++; }
}
inline int read()
{
int data = 0, w = 1;
char ch = IO::getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = IO::getchar();
if(ch == '-') w = -1, ch = IO::getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = IO::getchar();
return data*w;
}
const int maxn(40010);
struct edge { int next, to, dis; } e[maxn << 1];
int head[maxn], e_num, n, Size, Max, root, stk[maxn], dep[maxn], top, size[maxn], K, ans, vis[maxn];
inline void add_edge(int from, int to, int dis) { e[++e_num] = (edge) {head[from], to, dis}; head[from] = e_num; }
void GetRoot(int x, int fa)
{
size[x] = 1; int max = 0;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa || vis[to]) continue;
GetRoot(to, x); size[x] += size[to]; max = std::max(max, size[to]);
}
max = std::max(max, Size - size[x]);
if(max < Max) Max = max, root = x;
}
void GetDep(int x, int fa)
{
stk[++top] = dep[x];
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(to == fa || vis[to]) continue;
dep[to] = dep[x] + e[i].dis; GetDep(to, x);
}
}
int Calc(int x, int pre)
{
top = 0; dep[x] = pre; GetDep(x, 0); std::sort(stk + 1, stk + top + 1);
int l = 1, r = top, sum = 0;
while(l < r) { if(stk[l] + stk[r] <= K) sum += r - l, ++l; else --r; }
return sum;
}
void Solve(int x)
{
ans += Calc(x, 0); vis[x] = 1;
for(RG int i = head[x]; i; i = e[i].next)
{
int to = e[i].to; if(vis[to]) continue;
ans -= Calc(to, e[i].dis); Size = Max = size[to];
GetRoot(to, x); Solve(root);
}
}
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
Max = Size = n = read();
for(RG int i = 1, a, b, c; i < n; i++)
a = read(), b = read(), c = read(), add_edge(a, b, c), add_edge(b, a, c);
K = read(); GetRoot(1, 0); Solve(root); printf("%d\n", ans);
return 0;
}
|