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
| #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; struct edge { int v, w, nxt; } e[20001]; struct treap { int tot, root; struct node_type { int val, cnt, size, rank, child[2]; } a[10001]; void init() { tot = root = 0; } void update(int t) { a[t].size = a[a[t].child[0]].size + a[a[t].child[1]].size + a[t].cnt; } void turn(int &t, int dire) { int p = a[t].child[!dire]; a[t].child[!dire] = a[p].child[dire], a[p].child[dire] = t; update(t), update(p), t = p; } void insert(int &t, int val) { if (!t) { t = ++tot, a[t].rank = rand(), a[t].cnt = a[t].size = 1, a[t].val = val; a[t].child[0] = a[t].child[1] = 0; return; } ++a[t].size; if (val == a[t].val) ++a[t].cnt; else if (val < a[t].val) { insert(a[t].child[0], val); if (a[a[t].child[0]].rank < a[t].rank) turn(t, 1); } else { insert(a[t].child[1], val); if (a[a[t].child[1]].rank < a[t].rank) turn(t, 0); } } int query(int t, int val) { if (!t) return 0; if (val == a[t].val) return a[a[t].child[0]].size; else if (val < a[t].val) return query(a[t].child[0], val); else return a[a[t].child[0]].size + a[t].cnt + query(a[t].child[1], val); } } tree; long long n, k, nume, root, tot, ans, h[10001], size[10001], f[10001], val[10001]; bool vis[10001]; void add_edge(int u, int v, int w) { e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume; e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume; } void get_root(int t, int fa) { size[t] = 1, f[t] = 0; for (int i = h[t]; i; i = e[i].nxt) { if (!vis[e[i].v] && e[i].v != fa) { get_root(e[i].v, t); size[t] += size[e[i].v]; f[t] = max(f[t], size[e[i].v]); } } f[t] = max(f[t], tot - size[t]); if (f[t] < f[root]) root = t; } void get_dist(int t, int fa, int flag) { if (!flag) tree.insert(tree.root, val[t]); else ans += tree.query(tree.root, k - val[t] + 1); for (int i = h[t]; i; i = e[i].nxt) { if (!vis[e[i].v] && e[i].v != fa) { val[e[i].v] = val[t] + e[i].w; get_dist(e[i].v, t, flag); } } } void solve(int t) { vis[t] = true; tree.init(), tree.insert(tree.root, 0); for (int i = h[t]; i; i = e[i].nxt) { if (!vis[e[i].v]) { val[e[i].v] = e[i].w; get_dist(e[i].v, t, 1); get_dist(e[i].v, t, 0); } } for (int i = h[t]; i; i = e[i].nxt) { if (!vis[e[i].v]) { root = 0, tot = size[e[i].v]; get_root(e[i].v, t); solve(root); } } } int main() { while (scanf("%lld%lld", &n, &k)) { if (!n) break; memset(vis, 0, sizeof(vis)); memset(h, 0, sizeof(h)); ans = nume = 0; for (int i = 1; i < n; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add_edge(u ,v, w); } tot = f[0] = n, root = 0; get_root(1, 0); solve(root); printf("%lld\n", ans); } return 0; }
|