Background

TJOI2019 D2T3.

Source file name: segment.*.

Time limit: 4 s. Memory limit: 128 M.

Problem Description

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.

Input Format

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.

Output Format

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

8
3 1 1 1
3 1 1 2
3 1 2 1
3 1 2 2
3 2 4 1
3 2 4 2
3 1 5 1
3 1 5 2

1
0
3
1
6
2
8
0

Hint

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