#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,a,b) for (int i = a; i < b; ++i) #define RFOR(i,a,b) for(int i = a; i >= b;--i) #define REP(i, n) FOR(i, 0, n) #define rep(i,n) REP(i,n) #define forn(i,a,b) FOR(i,a,b) #define rfor(i,a,b) RFOR(i,a,b) #define f first #define s second #define ll long long #define pb push_back #define mp make_pair #define pii pair #define sz(f) (int)f.size() #define vi vector < int > #define db(x) cerr << #x << " = " << x << endl #define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; #define y1 jaksflkajsf #define pii pair #define pli pair const int INF = 1e9/2; const int inf = 1e9; const int N = 4e6+5; const double PI = acos(-1.0); const int MOD = 1000000000+7; struct edge{ int u, v, c; edge() {} bool operator < (const edge &a) { return this->c < a.c; } }; struct query{ int d, u, k; int id; query() {} query(int d, int u, int k, int id) : d(d), u(u), k(k), id(id) {} }; pii tree[N]; int cnt[N], all[N]; int timer; int Q, X, n, m, nold, qs; vi g[N]; edge a[N]; int f[N], tin[N], tout[N]; int cur[N]; query q[N]; int t; void clearTree(int v, int l, int r) { if (l == r) { tree[v] = mp(0, 0); return; } int m = (l + r) >> 1; clearTree(v + v, l, m); clearTree(v + v + 1, m + 1, r); //all[v] = tree[v] = cnt[v] = -1; } void clearTest() { clearTree(1, 0, n - 1); REP(i, n) g[i].clear(); timer = 0; memset(tin, 0, sizeof(tin)); memset(tout, 0, sizeof(tout)); memset(cur, 0, sizeof(cur)); memset(cnt, 0, sizeof(cnt)); } bool cmpK(query a, query b) { return a.k < b.k; } bool cmpId(query a, query b) { return a.d < b.d || (a.d == b.d && a.id < b.id) || (a.d == b.d && a.id == b.id && a.k > b.k); } int fs(int n) { if (f[n] == n) return n; f[n] = fs(f[n]); return f[n]; } void dfs(int v, int p = -1) { cur[timer] = v; tin[v] = timer++; REP(i, sz(g[v])) { int to = g[v][i]; if (to == p) continue; dfs(to, v); } tout[v] = timer - 1; } pii combine(pii a, pii b) { if(a.f > b.f) return b; if(a.f < b.f) return a; return mp(a.f,b.s+a.s); } void build(int v, int l, int r) { if (l == r) { int t = 0; if (cur[l] < nold) t = 1; tree[v] = mp(0, t); cnt[v] = 0; return; } int m = (l + r) / 2; build(v + v, l, m); build(v + v + 1, m + 1, r); tree[v] = combine(tree[v + v], tree[v + v + 1]); cnt[v] = 0; } void push(int v, int l, int r) { if (cnt[v] != 0) { if (l != r) { tree[v + v].first += cnt[v]; tree[v + v + 1].first += cnt[v]; cnt[v + v] += cnt[v]; cnt[v + v + 1] += cnt[v]; } cnt[v] = 0; } } void update(int v, int l, int r, int left, int right, int c) { push(v, l, r); if (l == left && r == right) { tree[v].first += c; cnt[v] = c; push(v, l, r); return; } int m = (l + r) >> 1; if (m >= right) update(v + v, l, m, left, right, c); else if (m < left) update(v + v + 1, m + 1, r, left, right, c); else { update(v + v, l, m, left, m, c); update(v + v + 1, m + 1, r, m + 1, right, c); } tree[v] = combine(tree[v + v], tree[v + v + 1]); } pii get(int v, int l, int r, int left, int right) { push(v, l, r); if (l == left && r == right) return tree[v]; int m = (l + r) >> 1; if (m >= right) return get(v + v, l, m, left, right); if (m < left) return get(v + v + 1, m + 1, r, left, right); pii ret = combine(get(v + v, l, m, left, m), get(v + v + 1, m + 1, r, m + 1, right)); tree[v] = combine(tree[v + v], tree[v + v + 1]); return ret; } vi solve() { scanf("%d", &n); REP(i, n - 1) { scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].c); a[i].u--; a[i].v--; } sort(a, a + n - 1); REP(i, n) f[i] = i; scanf("%d%d", &Q, &X); REP(i, Q) { scanf("%d%d%d", &q[i].d, &q[i].u, &q[i].k); q[i].u--; q[i].id = i; } sort(q, q + Q, cmpK); int j = 0; qs = Q; nold = n; REP(i, Q) { while (j < nold - 1 && a[j].c <= q[i].k) { int u = fs(a[j].u); int v = fs(a[j].v); if (u != v) { f[n] = n; f[u] = n; f[v] = n; g[n].pb(u); g[n].pb(v); n++; } j++; } q[i].u = fs(q[i].u); if (X != 0) q[qs++] = query(q[i].d + X, q[i].u, -1, -1); } while (j < nold - 1) { int u = fs(a[j].u); int v = fs(a[j].v); if (u != v) { f[n] = n; f[u] = n; f[v] = n; g[n].pb(u); g[n].pb(v); n++; } j++; } dfs(n - 1, -1); vi ret; build(1, 0, n - 1); sort(q, q + qs, cmpId); //REP(i, qs) // cout << q[i].d << " " << q[i].u << " " << q[i].k << " " << q[i].id << endl; REP(i, qs) { if (q[i].k == -1) { int cur = q[i].u; int left = tin[cur]; int right = tout[cur]; if (X != 0) update(1, 0, n - 1, left, right, -1); continue; } int cur = q[i].u; //cout << "C: " << cur << endl; //cout << tin[cur] << " " << tout[cur] << endl; int left = tin[cur]; int right = tout[cur]; pii ans = get(1, 0, n - 1, left, right); if (X != 0) update(1, 0, n - 1, left, right, 1); if (ans.f != 0) ans.second = 0; ret.pb(ans.second); } clearTest(); return ret; } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); scanf("%d", &t); REP(it, t) { vi ans = solve(); REP(i, sz(ans)) printf("%d\n", ans[i]); } return 0; }