据说是男人八题。
状态太差调了一节宝贵的晚自习，严重不开心。
异常裸的点分治。然后里面还是套的sbt。
卡空间比较丧病，不能开nlogn，要想办法开到n。其实就是找重心分治完再bfs一遍。最初没有写，所以mle爽，在poj上还显示的是re。
然后各种逗的错误调啊调。把代码调得怪丑。我还是naive啊。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge {
int t, v;
edge *next;
};
const int maxn = 40009;
int n, k, ans;
int d[maxn], tvis, vis[maxn], vd[maxn], sz[maxn], qu[maxn];
edge *ep, *head[maxn], elst[maxn * 2];
#define update(_p_) (sz[_p_]=sz[ls[_p_]]+sz[rs[_p_]]+1)
namespace sbt {
const int maxnd = maxn * 2;
const int balc = 5;
int nst[maxnd], tn;
int ls[maxnd], rs[maxnd], vl[maxnd], sz[maxnd];
inline void lRot(int& p) {
int q = rs[p];
rs[p] = ls[q];
ls[q] = p;
update(p);
update(q);
p = q;
}
inline void rRot(int& p) {
int q = ls[p];
ls[p] = rs[q];
rs[q] = p;
update(p);
update(q);
p = q;
}
void init() {
tn = 0;
sz[0] = 0;
for (int i = 1; i < maxnd; ++ i)
nst[tn ++] = i;
}
inline void ins(int& p, int v) {
if (!p) {
p = nst[-- tn];
ls[p] = 0;
rs[p] = 0;
sz[p] = 1;
vl[p] = v;
}
else {
++ sz[p];
if (v < vl[p]) {
ins(ls[p], v);
if (sz[ls[p]] > sz[rs[p]] + balc)
rRot(p);
}
else {
ins(rs[p], v);
if (sz[ls[p]] + balc < sz[rs[p]])
lRot(p);
}
}
}
inline int cntLower(int p, int v) {
if (!p)
return 0;
else if (v < vl[p])
return cntLower(ls[p], v);
else
return sz[ls[p]] + 1 + cntLower(rs[p], v);
}
void cntEach(int p, int q, int v) {
if (!p)
return;
ans += cntLower(q, v - vl[p]);
cntEach(ls[p], q, v);
cntEach(rs[p], q, v);
}
void insEach(int p, int& q, int a) {
if (!p)
return;
ins(q, vl[p] + a);
insEach(ls[p], q, a);
insEach(rs[p], q, a);
nst[tn ++] = p;
}
void rmv(int p) {
if (!p)
return;
nst[tn ++] = p;
rmv(ls[p]);
rmv(rs[p]);
}
};
inline void addEdge(int u, int v, int w) {
ep-> t = v;
ep-> v = w;
ep-> next = head[u];
head[u] = ep ++;
}
void getCore(int p0, int& ht) {
int hd = 0, tl = 1, mv;
++ tvis;
qu[hd] = p0;
vis[p0] = tvis;
d[p0] = 1;
while (hd < tl) {
int p = qu[hd ++];
for (edge* e = head[p]; e; e = e-> next)
if (!vd[e-> t] && vis[e-> t] < tvis) {
d[e-> t] = d[p] + 1;
vis[e-> t] = tvis;
qu[tl ++] = e-> t;
}
}
ht = qu[tl - 1];
mv = tl;
for (int i = tl - 1; i >= 0; -- i) {
int p = qu[i], ms = 0;
sz[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (vis[e-> t] == tvis && d[e-> t] > d[p]) {
sz[p] += sz[e-> t];
if (ms < sz[e-> t])
ms = sz[e-> t];
}
if (max(ms, tl - sz[p]) < mv) {
mv = max(ms, tl - sz[p]);
ht = p;
}
}
}
void recoverTree(int p0, int dd, int& hr) {
int hd = 0, tl = 1;
qu[hd] = p0;
d[p0] = 0;
hr = 0;
while (hd < tl) {
int p = qu[hd ++];
-- vd[p];
sbt :: ins(hr, d[p]);
for (edge* e = head[p]; e; e = e-> next)
if (vd[e-> t] == dd) {
qu[tl ++] = e-> t;
d[e-> t] = d[p] + e-> v;
}
}
}
int calcTree(int p0, int d = 1) {
int ht, hr, rt = 0;
getCore(p0, ht);
rt = 0;
sbt :: ins(rt, 0);
vd[ht] = d;
for (edge* e = head[ht]; e; e = e-> next)
if (!vd[e-> t]) {
int r = calcTree(e-> t, d + 1);
sbt :: cntEach(r, rt, k - e-> v);
sbt :: insEach(r, rt, e-> v);
}
sbt :: rmv(rt);
recoverTree(p0, d, hr);
return hr;
}
int sov() {
ep = elst;
memset(head, 0, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(vd, 0, sizeof(vd));
scanf("%d", &n);
for (int i = 0; i < n - 1; ++ i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
scanf("%d", &k);
tvis = 0;
ans = 0;
int x = calcTree(1);
sbt :: rmv(x);
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
sbt :: init();
ep = elst;
printf("%d\n", sov());
}