AT_k2pc001_e4 虫歯(Cavity)

[problemUrl]: https://atcoder.jp/contests/k2pc-easy/tasks/k2pc001_e4 kyuridenamidaは, お菓子を食べ過ぎて1本の歯を虫歯にしてしまった. その歯がとても痛むので歯医者さんに治療してもらったところ, 歯の神経のうち $ N $ 箇所を治療してもらえた. kyuridenamidaの歯の神経は, 図$ 1 $に示すように, 深さが$ K $の完全二分木になっている. (二分木については, [Wikipediaのページ](http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8)などを参照せよ.) 図 $ 1 $ 彼の神経を表す二分木で, 深さが $ i $ で左から $ j $ 番目の神経を $ (i,j) $と表す(図 $ 2 $ ). このとき, 根に当たる神経 $ (0,1) $ に, 先祖を遡ってたどり着ける神経を, **虫歯神経**と呼ぶこととする. ただし, 虫歯神経の先祖が既に治療されている場合, その虫歯神経は根の神経 $ (0,\ 1) $ に辿りつけない. また, $ (0,\ 1) $自身が治療されていなければ, $ (0,\ 1) $ が自身にたどり着けるものとする. 図 $ 2 $ 根に辿り着ける虫歯神経の個数の総和を**歯の痛み**とする. あなたの仕事は, kyuridenamidaの虫歯の情報が与えらるので, その歯の痛みをkyuridenamidaに教えて上げることである. 痛みを伝える神経の数を, $ 1 $ 行に出力せよ. (答えが $ 32 $ bit整数型に収まらない可能性があることに注意せよ.) - $ 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 ``` ``` 2 ``` ``` 9 0 ``` ``` 1023 ``` ``` 3 2 1 2 3 7 ``` ``` 8 ``` 入出力例3に対応する図は以下のとおりである. ここで, 図の青丸は治療された神経を表し, 赤の×印は根に辿り着ける虫歯神経を表す. 

N/A

N/A