#3109. 「TJOI2019」甲苯先生的线段树

内存限制:128 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: LoveAmy

题目描述

大中锋走在路上见到正在战术后仰的甲苯先生。因为甲苯先生帮助他解决了祖传 Hello word! 的代码密码,大中锋想上前打个招呼。

甲苯先生突然举起喇叭说:「大家好,我是甲苯拦你斯特,是凯岩城的首席文化大使,七十二变显神通,百般武艺样样有,感受不一样的权游文化。」

这时甲苯先生看到了大中锋,激动的拉着大中锋说:「为了筹钱去北境打异鬼,我参加了今年下半年中外合写的 stl+ 项目,我将在项目中担任线段树的主写人,但是改写不是乱写,在我写的时候,发现线段树是一个满二叉树,如果让根节点编号为 1 ,对于一个编号为 x 的节点,令左孩子编号为 2x ,右孩子编号为 2x+1 时,现在在这个二叉树上有两个节点 a,b ,现在我想知道节点 a 到节点 b 之间一条路径编号和最小为多少?你要是不会就直接给我 328,我不知道什么是暗影崛起,也不知道什么是怪盗军团。」

大中锋回答:「那不就是求一条简单路径直接算吗?」甲苯先生:「那你求这颗满二叉树中还有多少条简单路径等于这个值?不知道了吧,给我 328,我到北境打赢异鬼,回到凯岩城我就还你,我们拦你斯特,有债必偿。」

大中锋为了不给甲苯先生 328,请求作为好朋友的你写一个程序能解决甲苯先生的问题。

简单路径指的是路径上各个顶点均不重复的路径。

输入格式

第一行一个正整数 T ,表示有 T 组测试数据。

接下来 T 行,每行包含 4 个正整数 d,a,b,c 。其中 d 表示满二叉树的树高, a,b 表示二叉树上的两个节点, c 表示要回答甲苯先生的问题类别, c=1 时,回答甲苯先生第一个问题(点 a 到点 b 的最小路径上的编号和), c=2 时,回答甲苯先生的第二个问题,即回答除了从点 a 到点 c 的路径外与点 a 到点 b 的最小编号路径有相同编号和的简单路径的条数。

输出格式

对于每组输入,输出一行,每行包含一个正整数,表示甲苯先生问题的答案。

样例

样例输入

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

样例解释

对于一颗深度为 3 的满二叉树,含有节点 1,2,3,4,5,6,7

节点 1 1 的路径编号和为 1 ,且没有其他路径编号和为 1
节点 1 2 的路径编号和为 1+2=3 ,存在路径 3-3 编号和为 3
节点 2 4 的路径编号和为 2+4=6 ,存在路径 2-1-3 和路径 6-6 编号和为 6
节点 1 5 的路径编号和为 1+2+5=8 ,存在路径 8-8 编号和为 8 ,但是节点 8 的深度为 4 不满足条件。

数据范围与提示

对于 20\% 的数据,仅存在 c = 1 的情况;

对于 20\% 的数据, d ≤ 10

对于 30\% 的数据, d ≤ 20

对于 40\% 的数据, d ≤ 25

对于 50\% 的数据, d ≤ 30

对于 100\% 的数据, T\le 10,d ≤ 50