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
124
125
126
127
128
129
| #include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::vector;
const int MAXN = 40001;
struct Edge
{
int v, w;
Edge *next;
} g[MAXN*2], *header[MAXN];
void AddEdge(const int x, const int y, const int w)
{
static int LinkSize;
Edge* const node = g+(LinkSize++);
node->v = y;
node->w = w;
node->next = header[x];
header[x] = node;
}
int n, K, ans, parent[MAXN];
bool mark[MAXN];
std::queue<int> Q;
int GetCore(const int root)
{
static int son[MAXN];
static std::stack<int> s;
int nodes = 0;
for (Q.push(root), parent[root] = -1; !Q.empty(); Q.pop())
{
const int u = Q.front();
s.push(u);
++nodes;
for (Edge *e = header[u]; e; e = e->next)
if (!mark[e->v] && parent[u] != e->v)
{
parent[e->v] = u;
Q.push(e->v);
}
}
int core, min = 0x3F3F3F3F;
for (; !s.empty(); s.pop())
{
const int u = s.top();
int cnt = 0, max = 0;
for (Edge *e = header[u]; e; e = e->next)
if (!mark[e->v] && parent[u] != e->v)
{
cnt += son[e->v];
max = std::max(max, son[e->v]);
}
max = std::max(max, nodes-(son[u] = cnt+1));
if (max < min)
min = max, core = u;
}
return core;
}
inline int calc(const vector<int>& v)
{
int res = 0;
for (int i = 0, j = static_cast<int>(v.size())-1; i < j; )
if (v[i] + v[j] <= K) res += j-i, ++i;
else --j;
return res;
}
void Solve(const int core)
{
static int dist[MAXN];
int ans0 = 0, ans1 = 0;
mark[core] = true;
vector<int> v;
for (Q.push(core), dist[core] = 0, v.push_back(0), parent[core] = -1; !Q.empty(); Q.pop())
{
const int u = Q.front();
for (Edge *e = header[u]; e; e = e->next)
if (!mark[e->v] && parent[u] != e->v)
{
parent[e->v] = u;
v.push_back(dist[e->v] = dist[u] + e->w);
Q.push(e->v);
}
}
std::sort(v.begin(), v.end());
ans0 = calc(v);
for (Edge *edge = header[core]; edge; edge = edge->next)
{
const int st = edge->v;
if (mark[st]) continue;
v.clear();
for (Q.push(st), v.push_back(dist[st]); !Q.empty(); Q.pop())
{
const int u = Q.front();
for (Edge *e = header[u]; e; e = e->next)
if (!mark[e->v] && parent[u] != e->v)
{
v.push_back(dist[e->v]);
Q.push(e->v);
}
}
std::sort(v.begin(), v.end());
ans1 += calc(v);
}
ans += ans0-ans1;
}
int main()
{
scanf("%d", &n);
for (int i = 1, x, y, w; i < n; ++i)
{
scanf("%d%d%d", &x, &y, &w);
AddEdge(x, y, w);
AddEdge(y, x, w);
}
scanf("%d", &K);
std::queue<int> Q;
for (Q.push(1); !Q.empty(); Q.pop())
{
const int core = GetCore(Q.front());
Solve(core);
for (Edge *e = header[core]; e; e = e->next)
if (!mark[e->v])
Q.push(e->v);
}
printf("%d", ans);
}
|
