Queries on a Binary Tree
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Let's consider a rooted binary tree with the following properties:
- The number of nodes and edges in the tree is infinite
- The tree root is labeled by 1
- A node labeled by v has two children: 2 × v (the left son of v) and 2 × v + 1 (the right son of v)
Here is an image of the first several tree layers of such a tree:
Let's consider four operations, that are allowed to apply during the tree traversal:
- move to the left son - move from v to 2 × v
- move to the right son - move from v to 2 × v + 1
- move to the parent as a left son - move from v to v / 2 if v is an even integer
- move to the parent as a right son - move from v to (v - 1) / 2 if v is an odd integer
It can be proven, that for any pair of two nodes u and v, there is only one sequence of such commands, that moves from u to v and visits each node of the tree at most once. Let's call such a sequence of commands a path configuration for a pair of nodes (u, v).
You are asked to process a series of the following queries:
You are given three integers n, u and v (1 ≤ u, v ≤ n). Count the pairs of nodes (w, t) (1 ≤ w, t ≤ n) such that the path configuration for (w, t) is the same with the path configuration for (u, v).
The first line of input contains an integer Q denoting the number of queries to process.
Each of the next Q lines contains three space-separated integers n, u and v denoting a query.
For each query, print the answer on a separate line.
- 1 ≤ Q ≤ 20000
- 1 ≤ u, v ≤ n ≤ 109
Input: 3 11 9 11 10 2 2 8 1 8 Output: 2 10 1
In the first query from the example test case, you should count pairs (5, 7) and (9, 11).
In the second query from the example test case, you should count the following pairs: (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9) and (10, 10).
In the third query from the example test case, you should only count a pair (1, 8).
|Tags||cook69, easy, kostya_by, lca|
|Time Limit:||1 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.