#include #include #include using namespace std; #define LIM 100111 #define K 20 #define INF (1<<30) // segtree with lazy propagation typedef pair res; res add(res a, res b) { if (a.first < b.first) return a; if (a.first > b.first) return b; return make_pair(a.first, a.second + b.second); } struct segtree { int i, j; res val; int del; segtree *l, *r; segtree(int i, int j): i(i), j(j) { int count; del = 0; if (j - i == 1) { l = r = NULL; val = make_pair(0, 1); } else { int k = i + j >> 1; l = new segtree(i, k); r = new segtree(k, j); val = add(l->val, r->val); } } void visit() { if (del) { val = make_pair(val.first + del, val.second); if (l) { l->del += del; r->del += del; } del = 0; } } void inc(int I, int J, int d) { if (I <= i && j <= J) { del += d; visit(); } else { visit(); if (!(j <= I || J <= i)) { l->inc(I, J, d); r->inc(I, J, d); val = add(l->val, r->val); } } } res query(int I, int J) { visit(); if (I <= i && j <= J) { return val; } else if (j <= I || J <= i) { return make_pair(INF, 0); } else { return add(l->query(I, J), r->query(I, J)); } } }; // required range operations segtree *seg; void rq_init(int n) { seg = new segtree(0, n); } int rq_query(int i, int j) { res p = seg->query(i, j+1); return p.first ? 0 : p.second; } void rq_inc(int i, int j, int d) { seg->inc(i, j+1, d); } // a "decrease" operation struct dec { int d, i, j; dec() {} dec(int d, int i, int j): d(d), i(i), j(j) {} }; // list of edges struct edge { int a, b, c; edge() {} edge(int a, int b, int c): a(a), b(b), c(c) {} }; bool compare(const edge& x, const edge& y) { return x.c < y.c; } edge edges[LIM]; // union find int parent[LIM]; int find(int n) { return parent[n] < 0 ? n : parent[n] = find(parent[n]); } int onion(int a, int b) { if (parent[a] == parent[b]) parent[b]--; if (parent[a] > parent[b]) { return parent[a] = b; } else { return parent[b] = a; } } // list of nodes struct node { int weight; int parent; int l, r; int anc[K]; // jump pointers int position; int leftmost; int rightmost; node() {} node (int weight, int l = -1, int r = -1): weight(weight), l(l), r(r), parent(-1), position(-1), leftmost(-1), rightmost(-1) {} }; node nodes[LIM<<1]; void init(int i, int pos) { // compute anc int j = nodes[i].anc[0] = nodes[i].parent; for (int k = 1; k < K; k++) { j = nodes[i].anc[k] = nodes[j].anc[k-1]; } // position nodes[i].position = pos; } // uses jump pointers to get the relevant subtree int R; int find_root(int u, int w) { if (nodes[R].weight <= w) return R; int k = 0; while (nodes[nodes[u].anc[k]].weight <= w) { u = nodes[u].anc[k++]; } while (k--) if (nodes[nodes[u].anc[k]].weight <= w) { u = nodes[u].anc[k]; } return u; } // solve a single test case bool vis[LIM]; int root[LIM]; void solve() { int n; scanf("%d", &n); int N = n; for (int i = 0; i < n; i++) { parent[i] = -1; nodes[i] = node(0); root[i] = i; } // edges for (int i = 0; i < n-1; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a--, b--; edges[i] = edge(a, b, c); } // sort edges sort(edges, edges + n-1, compare); // construct reachability tree for (int i = 0; i < n-1; i++) { int a = find(edges[i].a); int b = find(edges[i].b); int weight = edges[i].c; int k = onion(a, b); nodes[N] = node(weight, root[a], root[b]); nodes[root[a]].parent = nodes[root[b]].parent = N; root[k] = N++; } R = N-1; // root of reachability tree nodes[R].parent = R; // set root's parent as itself for (int i = 0; i < N; i++) { vis[i] = false; } // preorder trversal. 'pre' will contain the leaves vector stack; vector pre; stack.push_back(R); int pos = 0; while (!stack.empty()) { int i = stack.back(), j; stack.pop_back(); pre.push_back(i); init(i, pos); if (i < n) pos++; // it means 'i' is a leaf if (~(j = nodes[i].r) && !vis[j]) { vis[j] = true; stack.push_back(j); } if (~(j = nodes[i].l) && !vis[j]) { vis[j] = true; stack.push_back(j); } } // compute leftmost and rightmost for (int f = N-1; f >= 0; f--) { int i = pre[f]; nodes[i].leftmost = ~nodes[i].l && ~nodes[nodes[i].l].leftmost ? nodes[nodes[i].l].leftmost : nodes[i].position; nodes[i].rightmost = ~nodes[i].r && ~nodes[nodes[i].r].rightmost ? nodes[nodes[i].r].rightmost : nodes[i].position; } // answer queries int q, x; scanf("%d%d\n", &q, &x); rq_init(n); vector decs; // list of decrease operations for (int f = 0; q--;) { int d, u, w; scanf("%d%d%d", &d, &u, &w); u--; u = find_root(u, w); // range decreases for (; f < decs.size() && decs[f].d <= d; f++) { rq_inc(decs[f].i, decs[f].j, -1); } // range query int i = nodes[u].leftmost, j = nodes[u].rightmost; printf("%d\n", rq_query(i, j)); // range increase rq_inc(i, j, +1); // future "range decrease" decs.push_back(dec(d+x, i, j)); } } int main() { int z; scanf("%d", &z); while (z--) solve(); }