來算算看用陣列跑K次的時間複雜度，總共Q筆詢問每次最多傳送K次，數字帶進去$O(NQ)=10^5\times 10^9=$可怕的$10^14$，也難怪會TLE

那當然，就需要一個不需要一次一次慢慢跳跳K次的方法，都寫在題名上了，就是蓋倍增表

假設要K=7，我們可以這樣跳

4 + 2 + 1

這樣只需要做三次

一格一格跳需要7次，光數字這麼小就有這麼大的差距，K到幾百萬量級的時候會更明顯

應該不難發現4跟2跟1都是2的次方，倍增表在做的事就是對K做二進位分解，每次都跳二的次方格，可以大大的降低時間複雜度，具體速度會變多快? 會從$O(K) \rightarrow O(log k)$ (log以二為底)

再來就是怎麼一次跳$2^x$，問題好像又回到不能慢慢跳的問題了，但我們可以預處理阿，想像一下:

跳一次怎麼轉變成跳兩次 (跳一次再跳一次)

跳兩次怎麼轉變成跳四次 (跳兩次再跳兩次)

跳四次怎麼轉變成跳八次 (跳四次再跳四次)

... 以此類推

所以我們需要預先建好一個陣列，記錄每一個節點跳$2^x for x in range(1,\lfloor log(10^9) \rfloor)$次是多少

建的方法按照上面，jmp[x][i]=jmp[x-1][jmp[x-1][i]]這樣(x是2的次方數，i是節點)，預處理的時間複雜度是$O(NlogK)$ *N是節點個數

之後每筆查詢對K做二進位分解去跳就能在$O(NlogK + QlogK)$的時間內解掉這題了

開溜~