#P5342. [TJOI2019] 甲苯先生的线段树

[TJOI2019] 甲苯先生的线段树

题目背景

TJOI2019 D2T3

源文件名:segment.*

时间限制: 4s 内存限制: 128M

题目描述

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

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

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

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

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

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

输入格式

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

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

输出格式

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

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

提示

样例解释

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

节点 1111 的路径编号和为 11 ,且没有其他路径编号和为 11

节点 1122 的路径编号和为 1+2=31+2=3 ,存在路径 3-3 编号和为 33

节点 2244 的路径编号和为 2+4=62+4=6 ,存在路径 2-1-3 和路径 6-6 编号和为 66

节点 1155 的路径编号和为 1+2+5=81+2+5=8 ,存在路径 8-8 编号和为 88 ,但是节点 88 的深度为 44 不满足条件。

数据范围

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

对于 20%20\% 的数据, d10d \leq 10

对于 30%30\% 的数据, d20d \leq 20

对于 40%40\% 的数据, d25d \leq 25

对于 50%50\% 的数据, d30d \leq 30

对于 100%100\% 的数据, d50,T10d \leq 50,T \leq 10