962 . 完美二元樹
TopCoder
Tags
Description
給你一棵深度為 $d$ 的完美二元樹，請支援 $q$ 筆操作，每次操作會在這張圖上加一條新的邊，你能在每次加邊完後都回答根到所有點的最短距離總和嗎？每一條邊都是無向邊且邊權為 $1$。
一個深度為 $d$ 的完美二元樹有 $2^ d - 1$ 個節點，$2^ d - 2$ 條邊。令節點的編號為 $1, 2, \ldots, 2^ d - 1$，節點 $1$ 為根且第 $i$ 條邊連接節點 $\lfloor \frac{i + 1}{2} \rfloor$ 與節點 $i + 1$。兩節點 $u$ 與 $v$ 的最短距離為最少需要經過幾條邊才能從 $u$ 走到 $v$。
Input Format
第一行有兩個正整數 $d, q$，代表完美二元樹的深度與操作的數量。
接下來 $q$ 行，每行有兩個正整數 $u, v$，代表該筆操作增加一條從 $u$ 到 $v$ 的邊。可能會有重邊。
- $2 \leq d \leq 20$
- $1 \leq q \leq 5 \times 10^ 5$
- $1 \leq u \neq v < 2^ d$
Output Format
請輸出 $q$ 行，其中第 $i$ 行代表進行前 $i$ 個操作後，根到所有節點的最短距離總和。
Sample Input 1
4 5 1 5 6 1 2 14 1 8 3 4
Sample Output 1
31 28 27 25 25
Sample Input 2
2 3 3 2 2 3 3 2
Sample Output 2
2 2 2
Sample Input 3
7 10 72 23 43 9 102 9 60 8 1 38 27 19 29 94 38 10 27 84 112 25
Sample Output 3
641 638 636 633 613 606 605 593 592 591
Hints
在第一筆範例測資中，令 $d$ 為一序列且 $d_i$ 為節點 1 到節點 $i$ 的最短距離。則：
- 在所有加邊操作前，$d = [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3]$
- 在第一次操作後，$d = [0, 1, 1, 2, 1, 2, 2, 3, 3, 2, 2, 3, 3, 3, 3]$，答案為 $31$
- 在第二次操作後，$d = [0, 1, 1, 2, 1, 1, 2, 3, 3, 2, 2, 2, 2, 3, 3]$，答案為 $28$
- 在第三次操作後，$d = [0, 1, 1, 2, 1, 1, 2, 3, 3, 2, 2, 2, 2, 2, 3]$，答案為 $27$
- 在第四次操作後，$d = [0, 1, 1, 2, 1, 1, 2, 1, 3, 2, 2, 2, 2, 2, 3]$，答案為 $25$
- 在第五次操作後，$d = [0, 1, 1, 2, 1, 1, 2, 1, 3, 2, 2, 2, 2, 2, 3]$，答案為 $25$
Problem Source
YTP 2025 高中組程式挑戰營 p12
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測試資料 | 0 |
| 2 | 0~27 | 無額外限制 | 15 |