← 返回题目列表

AtCoder · k2pc001_e4

D. 腔体

中文机器翻译题面 查看原题

問題文

Kyuridenamida 吃了太多甜食,他的一颗牙齿出现了蛀牙。
牙齿很痛,所以去看牙医治疗,牙齿里的神经 N 该区域已接受治疗。

kyuridenamida 的牙神经,图 1。 如1所示,深度为K是一个完全二叉树。
(对于二叉树, 维基百科页面 参见等)

図 1

代表他的神经的二叉树,深度为 i 从左起 j 第神经 (i,j)(图. 2 ).
此时根部对应的神经 (0,1) ,让你追溯祖先的神经, 我们称之为 虫歯神経。
然而,如果龋神经的祖先已经被治疗,则龋神经将成为根神经。 我无法联系到 (0, 1) 。
另外, (0, 1)如果你自己没有得到对待, 假定 (0, 1) 能够到达自身。

図 2

可以到达牙根的龋齿神经总数。牙痛。 如果
你的工作是告诉 kyuridenamida 牙齿疼痛,因为你得到了有关 kyuridenamida 牙齿蛀牙的信息。


入力

K
N
p_1 q_1
p_2 q_2
.
.
.
p_N q_N
  • 1 第 1 行包含一个表示神经深度的整数。 写入K。
  • 2 第 1 行包含一个整数,表示治疗的神经数量。N。
  • 继续 N 行包含一个整数,表示有关所治疗神经的信息。 p_i和 按字典顺序比较 q_i (1 ≦ i ≦ N) 之间用空格分隔。
    这是位置 (p_i,q_i) 表示神经正在接受治疗。

出力

传递疼痛的神经数量, 在 1 行输出。
(答案是 32 请注意,它可能不适合位整数类型。)

制約

  • 1 ≦ K ≦ 50 牙神经深度
  • 0 ≦ N ≦ 10^5 治疗神经的数量
  • 0 ≦ p_i ≦ K  治疗神经 i 深度
  • 1 ≦ q_i ≦ 2^{p_i} 治疗神经 i ,深度 位置在 p_i如果
  • p_i = p_j , q_i ≠ q_j有保证。

部分点

积分分配 40% 分钟, 当 N ≦ 1000 很满意。


入力例 1

1
1
1 1

出力例 1

2

入力例 2

9
0

出力例 2

1023

入力例 3

3
2
1 2
3 7

出力例 3

8

提示

对应于输入/输出示例3的图如下所示。
这里,图中的蓝色圆圈代表治疗的神经,红色的x标记代表可以追溯到根部的龋齿神经。

(故事)kagamiz
(问题)kagamiz
(测试仪)fura2