All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Paavini, Nupur, Anchal and Ishita are four best friends and roommates. In their normal routine, they only study and study and do nothing else. But now that exams are over, they want to explore the town, so they went to the Trade Fair to eat.
The trade fair has N halls and it's represented by a tree with N vertices and N-1 edges. Each edge contains exactly one restaurant offering only meals of one type at a fixed cost.
Since Bhavya and Kaushal didn't go along with them, they have asked Q queries. Each query is given as follows: The friends move from hall U to hall V along the shortest path. From each restaurant they encounter on this path, they will purchase exactly one meal in total if its cost C satisfies the following conditions:
- If C is a multiple of 2, C must be between X1 and Y1 inclusive.
- If C is a multiple of 3, C must be between X2 and Y2 inclusive.
- If C is a multiple of 5, C must be between X3 and Y3 inclusive.
- C must be a multiple of 2, 3 or 5.
For each query, compute the total cost of all meals bought when travelling from U to V. you have the answer the queries in online mode.
- U = in1 + last
- V = in2 + last
- X1 = in3 + last
- Y1 = in4 + last
- X2 = in5 + last
- Y2 = in6 + last
- X3 = in7 + last
- Y3 = in8 + last
For each query, print the answer to it on a separate line.
- 1 ≤ N, Q ≤ 50,000
- 1 ≤ U, V ≤ N
- 1 ≤ C ≤ 40,000
- 1 ≤ Xi ≤ Y i ≤ 40,000, for each 1 ≤ i ≤ 3
Subtask #1 (20 points): 1 ≤ N, Q ≤ 1000
Subtask #2 (80 points): original constraints
Input: 3 2 1 2 6 1 3 11 2 3 2 20 3 20 2 4 -4 -3 -4 14 -3 -1 -4 -2 Output: 6 0
For the first query, they will eat at the restaurant connecting halls 1 and 2; the cost of the meal there is 6.
For the second query, 6 is a multiple of 3, but according to the second condition, the cost of this meal isn't between 3 and 5. Hence they will not eat at any restaurant.
|Tags||abx_2109, binary-search, dfs, inclusion-exclusion, lca, ltime55, medium-hard|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.