P5342 [TJOI2019] Mr. Toluene’s Segment Tree

TJOI2019 D2T3. Source file name: segment.*. Time limit: 4 s. Memory limit: 128 M.

Da Zhongfeng was walking on the road and saw Mr. Toluene doing a tactical fadeaway. Because Mr. Toluene helped him crack the code password of the family-inherited `Hello word!`, Da Zhongfeng wanted to go up and say hello. Mr. Toluene suddenly raised a loudspeaker and said: “Hello everyone, I am Toluene Lannister, the chief cultural ambassador of Casterly Rock. I can transform in seventy-two ways, and I am good at all kinds of skills. Feel a different Game of Thrones culture.” At this time, Mr. Toluene saw Da Zhongfeng and excitedly grabbed him and said: “To raise money to go to the North to fight the White Walkers, I joined the `stl+` project co-written by China and foreign teams in the second half of this year. I will be the main writer of the segment tree in the project. But rewriting is not random writing. When I was writing, I found that a segment tree is a perfect binary tree. If we label the root as $1$, then for a node labeled $x$, let the left child be labeled $2x$ and the right child be labeled $2x+1$. Now, in this binary tree there are two nodes $a, b$. I want to know: along the path from node $a$ to node $b$, what is the minimum possible value of the sum of node labels on that path? If you can’t do it, just give me 328. I don’t know what Shadowbrink Rising is, and I don’t know what the Phantom Thief Legion is either.” Da Zhongfeng replied: “Isn’t that just computing a simple path directly?” Mr. Toluene said: “Then tell me how many simple paths in this perfect binary tree are equal to this value? You don’t know, right? Give me 328. After I defeat the White Walkers in the North and return to Casterly Rock, I will pay you back. We Lannisters always pay our debts.” To avoid giving Mr. Toluene 328, Da Zhongfeng asked you, as a good friend, to write a program to solve Mr. Toluene’s problem. A simple path means a path in which no vertex repeats.

The first line contains a positive integer $T$, meaning there are $T$ test cases. Next, there are $T$ lines. Each line contains $4$ positive integers $d, a, b, c$. Here, $d$ is the height of the perfect binary tree, $a, b$ are two nodes in the binary tree, and $c$ indicates which type of question Mr. Toluene asks. When $c=1$, answer Mr. Toluene’s first question (the minimum sum of labels on the path from node $a$ to node $b$). When $c=2$, answer Mr. Toluene’s second question, i.e., the number of simple paths that have the same label-sum as the minimum-label-sum path from node $a$ to node $b$, excluding the path from node $a$ to node $b$ itself.

For each test case, output one line containing one positive integer, the answer to Mr. Toluene’s question.

### Sample Explanation For a perfect binary tree of depth $3$, it contains nodes $1, 2, 3, 4, 5, 6, 7$. The label-sum of the path from node $1$ to node $1$ is $1$, and there is no other path whose label-sum is $1$. The label-sum of the path from node $1$ to node $2$ is $1+2=3$. There exists a path $3-3$ whose label-sum is $3$. The label-sum of the path from node $2$ to node $4$ is $2+4=6$. There exist the path $2-1-3$ and the path $6-6$ whose label-sum is $6$. The label-sum of the path from node $1$ to node $5$ is $1+2+5=8$. There exists a path $8-8$ whose label-sum is $8$, but node $8$ has depth $4$, which does not satisfy the condition. ### Constraints For $20\%$ of the testdata, there are only cases with $c = 1$. For $20\%$ of the testdata, $d \leq 10$. For $30\%$ of the testdata, $d \leq 20$. For $40\%$ of the testdata, $d \leq 25$. For $50\%$ of the testdata, $d \leq 30$. For $100\%$ of the testdata, $d \leq 50, T \leq 10$. Translated by ChatGPT 5