laekov

据说是男人八题。

状态太差调了一节宝贵的晚自习，严重不开心。

异常裸的点分治。然后里面还是套的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());

}