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 N-1 trails. The nodes are numbered from 1 to N. Each trail i connects two different nodes, ui and vi and has length Li. 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 dj, Cherry will start at a node uj and visit all the nodes she can reach while taking only the trails whose length does not exceed kj. 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 dj+X, then it will have a fully grown tulip on that day. On day d1, 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.
- 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 N-1 lines describe the edges. The i+1th line contains three space separated integers ui, vi and Li.
- 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 jth such line contains three space separated integers dj, uj and kj.
- For each test case, output Q lines.
- The jth line of each test case should contain the number of tulips Cherry collects on day dj.
- 1 ≤ T ≤ 10
- 1 ≤ N,Q ≤ 105
- 1 ≤ ui,vi ≤ N
- 1 ≤ Li,kj ≤ 108
- 1 ≤ d1 ≤ 108
- dj-1 < dj ≤ 108 for 2 ≤ j ≤ Q
- Subtask 1: X = 1 (15 points)
- Subtask 2: 1 ≤ X ≤ 108 (85 points)
Input: 1 3 1 2 7 3 1 10 3 4 5 2 8 7 1 20 13 2 3 Output: 2 1 1
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 3-1 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.
|Tags||centroid-decomp, disjoint-set, hard, march16, meteora, segment-tree|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.