Tiptoe through the tulips

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Cherry has discovered the Garden of Magical Tulips while going on a walk. The garden can be described as N nodes connected by N1 trails. The nodes are numbered from 1 to N. Each trail i connects two different nodes, u_{i} and v_{i} and has length L_{i}. It is possible to visit all the nodes starting from any node using a sequence of trails.
Magical tulips like to grow alone, without being disturbed. So, every node has exactly one tulip growing there peacefully and a tulip never withers once it is fully grown. If a fully grown tulip is picked, a new one will grow in the same spot if it is left undisturbed for X contiguous days.
Sometimes, when Cherry goes for a walk, she visits the garden to collect some tulips for her beloved Jimma, who is always waiting at the window to see Cherry pass by. The number of tulips she collects on a particular day depends on her mood. She gets bored while walking on long trails, so on day d_{j}, Cherry will start at a node u_{j} and visit all the nodes she can reach while taking only the trails whose length does not exceed k_{j}. She will pick all the fully grown tulips she can find. But in the process, she might visit some nodes which do not have a fully grown tulip yet. These tulips will get upset and grow fully only after X days if Cherry doesn't disturb them again before that.
i.e. if Cherry does not visit that node again before the day d_{j}+X, then it will have a fully grown tulip on that day. On day d_{1}, all the nodes have fully grown tulips.
Cherry has never been to school and is not very good at counting, so she always wonders how many tulips she has collected. Please help Cherry figure out the number of tulips she collects for the next Q days she visits the garden.
Input
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains a single integer N. The next N1 lines describe the edges. The i+1^{th} line contains three space separated integers u_{i}, v_{i} and L_{i}.
 The next line contains two space separated integers Q and X and is followed by Q lines each describing the next Q days Cherry visits the garden. The j^{th} such line contains three space separated integers d_{j}, u_{j} and k_{j}.
Output
 For each test case, output Q lines.
 The j^{th} line of each test case should contain the number of tulips Cherry collects on day d_{j}.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N,Q ≤ 10^{5}
 1 ≤ u_{i},v_{i} ≤ N
 1 ≤ L_{i},k_{j} ≤ 10^{8}
 1 ≤ d_{1} ≤ 10^{8}
 d_{j1} < d_{j} ≤ 10^{8} for 2 ≤ j ≤ Q
Subtasks
 Subtask 1: X = 1 (15 points)
 Subtask 2: 1 ≤ X ≤ 10^{8} (85 points)
Example
Input: 1 3 1 2 7 3 1 10 3 4 5 2 8 7 1 20 13 2 3 Output: 2 1 1
Explanation
Example case 1. There are 3 queries. The tulips take 4 days to grow fully. In the first query, Cherry will visit nodes 1 and 2, because the trail 31 has length greater than 8. Both the nodes will have fully grown tulips. After Cherry picks them, the tulips will grow back on day 5+4, if Cherry doesn't visit them again. So the output is 2.
In the second query, Cherry will visit all the trails because all of them have length less than 20. The tulips at 1,2 haven't grown back yet and now all the tulips will take 4 more days. There is a tulip at 3. So the output is 1.
In the third query, on day 13, all the tulips have grown back, but Cherry will not use any of the trails because both of them have length greater than 3. So, she will collect only one tulip  the tulip at 2.
Author:  meteora 
Tester:  furko 
Editorial  http://discuss.codechef.com/problems/TULIPS 
Tags  centroiddecomp, disjointset, hard, march16, meteora, segmenttree 
Date Added:  10022016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 