# AP325 精熟到登峰 下篇

> 作者：沈宗叡（暴力又被TLE）

## 三、全題解

### [P-5-4. 反序數量](https://judge.tcirc.tw/problem/d064)

先複習一下 [上篇第二章](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part1#3-%E5%88%86%E6%B2%BB%E5%84%AA%E5%8C%96) 提到的分治優化方法：

>只要區間切得好，複雜度在 worst case 沒有爛掉，分治的理論複雜度通常不錯，但切到後面區間越來越短的時候，因為每層遞迴有較大的固定消耗，效率相對而言會越來越低。
所以區間足夠短的時候，可以用理論複雜度差一些但常數較小的演算法直接暴力解決。
除此之外，分治常常會搭配 merge sort 使用，而在大部分情況下，第一層遞迴（也就是完整的區間 $[0, n)$）是沒有必要將左右兩個區間 merge sort 的，可以省不少時間。

將以上思想套用進分治程式裡：
$Time: O(n \log_2 n), Space: O(n)$

def main():
    from sys import stdin
    from bisect import bisect_right
    e = stdin.readline

    def merge(s, t):  # -> list[int]
        nonlocal ans  # 宣告取上一層的 ans 變數
        if t - s <= 4096:
            # 區間夠小 直接暴力O(n²)
            res = []
            for i in range(s, t):
                v = l[i]
                idx = bisect_right(res, v)
                ans += len(res) - idx
                res.insert(idx, v)
            return res

        mid = s + t >> 1
        le = merge(s, mid)
        ri = merge(mid, t)
        x = len(le)  # 初始化反序對數量

        if s == 0 and t == n:
            # 第一層遞迴不用merge左右區間
            le, ri = iter(le), iter(ri)
            i, j = next(le), next(ri)
            while True:
                if i <= j:
                    x -= 1  # 反序對變少
                    i = next(le, None)
                    if i is None:
                        break
                else:
                    ans += x  # 加上反序數量
                    j = next(ri, None)
                    if j is None:
                        break
            return

        # 合併
        res = []
        le, ri = iter(le), iter(ri)
        i, j = next(le), next(ri)
        while True:
            if i <= j:
                x -= 1  # 反序對變少
                res.append(i)
                i = next(le, None)
                if i is None:
                    res.append(j)
                    res.extend(ri)
                    break
            else:
                ans += x  # 加上反序數量
                res.append(j)
                j = next(ri, None)
                if j is None:
                    res.append(i)
                    res.extend(le)
                    break
        return res

    n = int(e())
    l = tuple(map(int, e().split()))

    ans = 0
    merge(0, n)
    print(ans)
main()

這題也有分治以外的解法：使用 [BIT (Binary Indexed Tree)](https://cp.wiwiho.me/fenwick-tree/) （超綱），可以理解為帶修改的前綴和。

前綴和、BIT 的複雜度比較：

||建表|區間查詢|單點修改|空間|
|-|-|-|-|-|
|前綴和|$O(n)$|$O(1)$|$O(n)$|$O(n)$|
|BIT|$O(n)$|$O(\log_2n)$|$O(\log_2n)$|$O(n)$|

BIT 的基本模板：

# 初始化
bit = [0]  # 佔位 sentinel, BIT 為 1-based
bit.extend(a)  # a 為原數列
n = len(bit) - 1  # 原數列長度

# 建表 O(n)
# bottom-up contribute 的思想
for i, v in enumerate(bit):
    i += (i & -i)  # low-bit 取父節點
    if i <= n:  # 如果父節點存在
        bit[i] += v

# 查前綴和 O(logn)
# res = sum(a[:i+1])
res = 0
while i > 0:
    res += bit[i]
    i -= i & -i  # low-bit

# 單點更新 O(logn)
# a[i] += v
while i <= n:  # 注意 n 為閉區間
    bit[i] += v
    i += i & -i  # low-bit

有趣的是將查詢和更新對 `i` 的操作反過來就會變後綴和。

因此，我們可以定義 `a[i]` 為 `i` 這個數字之前出現過的次數，每次掃到一個數字的時候，先用 BIT 查詢 `sum(a[i+1:])`，再用 BIT 更新 `a[i] += 1`。

這種方法的缺點是：BIT 的大小需要開到 `max(a) - min(a)`，在離散的數列上空間複雜度直接炸掉。

$Time: O(n \log_2 \max(A)), Space: O(\max(A))$

def main():
    from sys import stdin
    e = stdin.readline

    e()
    l = tuple(map(int, e().split()))
    m = max(l)

    ans = 0
    size = m + 2
    bit = [0] * size  # 後綴和BIT
    for v in l:
        v += 1  # v可能是0 所以全部+1
        i = v + 1  # ==不能算 必須>
        while i < size:
            ans += bit[i]
            i += i & -i  # low-bit
        i = v
        while i > 0:
            bit[i] += 1
            i -= i & -i  # low-bit
    print(ans)
main()

有甚麼辦法可以解決這個缺點呢？離散化！因為數字本身的大小並不重要，只看數字之間的相對關係即可，因此將每個數字按照大小順序重新對應到一個小區間上，就解決問題了！

下面的解將 $A$ 去重後對應到 $[1:|\text{set}(A)|]$ 區間內。
$Time: O(n \log_2 n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    e()
    l = tuple(map(int, e().split()))
    # 將每個數字依照大小給予index 把BIT開小一點
    idx = {v: i for i, v in enumerate(sorted(set(l)), start=1)}
    get = idx.__getitem__

    ans = 0
    size = len(idx)
    bit = [0] * (size + 1)  # 後綴和BIT
    for v in map(get, l):
        i = v + 1  # ==不能算 必須>
        while i <= size:
            ans += bit[i]
            i += i & -i  # low-bit
        i = v
        while i > 0:
            bit[i] += 1
            i -= i & -i  # low-bit
    print(ans)
main()

或者換個角度思考：既然 BIT 有很多格都是 $0$，那就別開空間給他，只開空間給有用到的格子就好了，也就是將 `list` 改成 `dict`，變成一個「動態開點」的概念。（當然也可以只開到 $\max(A)$，這裡是想示範完全在線的概念）
小缺點是時間複雜度的 $\log$ 項變大了。

$Time: O(n \log_2 1e6), Space: O(n)$

def main():
    from sys import stdin
    from collections import defaultdict
    e = stdin.readline

    e()
    l = map(int, e().split())

    ans = 0
    size = 10 ** 6 + 2  # 數值最大範圍為 1e6
    bit = defaultdict(int)  # 後綴和BIT 動態開點
    for v in l:
        v += 1  # v可能是0 所以全部+1
        i = v + 1  # ==不能算 必須>
        while i < size:
            ans += bit.get(i, 0)
            i += i & -i  # low-bit
        i = v
        while i > 0:
            bit[i] += 1
            i -= i & -i  # low-bit
    print(ans)
main()

BIT 本身是一個好寫、常數小的優秀資料結構，可惜 python 的位元操作和列表操作都很慢，難以發揮 BIT 的優勢。這題最快的解是優化過後的分治。

### [P-5-5. 最靠近的一對](https://judge.tcirc.tw/problem/d056)

套上分治優化方法，$64$ 以內的區間暴力 $O(n^2)$。

這個解不是理論最佳，因為在 `46` 行的地方執行了 `it.sort()`，將區間對 `y` 排序，如果要理論最佳 $O(n \log_2 n)$ 的話，輸入點對後就存兩組數據，一組對 `x`、一組對 `y` 排序，而在 `46` 那部分則改成從對 `y` 排序的數據中，找出 `x` 在範圍內的，但就必須遍歷整組數據，可能會慢上不少。

在不少地方都用到了 `list[slice]` 的語法，雖然說這樣會建立一個新的 list object，但以下用到的地方區間長度都很小，這樣的寫法反而會比用 index 一個一個取值更快。

$Time: O(n (\log_2 n) ^ 2), Space: O(n)$

def main():
    from sys import stdin
    from operator import itemgetter
    e = stdin.readline

    def merge(s, t) -> None:
        nonlocal ans
        if s >= t:
            # 無法形成區間
            return

        if t - s <= 64:
            # 區間夠小 暴力O(n²)比較快
            for i in range(s, t - 1):
                x, y = l[i]
                for x_, y_ in l[i + 1:t]:
                    dx = x_ - x
                    if dx > ans: break
                    dx += abs(y_ - y)
                    if dx < ans: ans = dx
            return

        # 切一半分治
        mid = s + t >> 1
        merge(s, mid)
        merge(mid, t)

        # 特判結束條件
        if ans == 0: return

        # 合併
        # 由中線往左右找 x 在 mid.x ± ans 以內的點
        i = mid
        b = l[mid][0] - ans
        while i >= s and l[i][0] > b:
            i -= 1
        i += 1

        j = mid
        b += ans << 1  # mid.x + ans
        while j < t and l[j][0] < b:
            j += 1

        # 依照y升冪排列 (y本身隨x各自升冪 powersort起來很快)
        it = l[i:j]
        it.sort(key=itemgetter(1))
        for i, (x, y) in enumerate(it, start=1):
            # 只要往後看三個就可以
            for x_, y_ in it[i:i+3]:
                dy = y_ - y
                if dy > ans: break
                dy += abs(x_ - x)
                if dy < ans: ans = dy

    n = int(e())
    # x升冪 再y升冪
    l = sorted(tuple(map(int, e().split())) for i in range(n))

    ans = float("INF")
    merge(0, n)
    print(ans)
main()

WIP：隨機期望 $O(n)$ 解法
WIP：人類智慧 解法

### [P-5-7. 大樓外牆廣告](https://judge.tcirc.tw/problem/d065)

分治的程式碼跟教授的大差不差，我這裡就放 $O(n)$ 的單調棧解法。

以掃描線的思維可以發現：如果往右掃的時候，新的大樓比先前的低，高度就必須壓到和新的大樓一樣高，而先前較高樓的高度就無用了。

    5              5  
  4 |            4 |  
  # #            | |
  # # 2   ->     | | 2
1 # # |        1 # # #
| # # |        | # # #

對於每個大樓來說，以他的高度貼海報，寬度可以從「左側第一個比他矮的」到「右側第一個比他矮的」，因此我們可以維護一個單調遞增的 Stack，在 `pop` 掉舊高樓時，個別結算以他們的高度貼海報、從貼到緊靠著新大樓左端（也就是新大樓之前）形成的最大面積。

這題比較特別的是更新答案用到了 `Stack[-2]` 的位置、`Stack[-1]` 的高度、`i - 1` 的位置，並且是在 `while ... pop` 的過程中更新。

`if pv == v` 的 case 也可以直接省略，一律 `append` 就好，但這樣可以在某些 case 下省時間也省空間，主要想傳達的訊息是「不要忘記考慮 `pv == v` 的 case」，雖然在這題沒有差異，[後面有一題](#088) 就會有差。

這題我的 sentinel 設計地十分巧妙，讀者可以自行體會體會（燦笑推眼鏡）。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    l = list(map(int, e().split()))
    l.append(0)  # sentinel 確保結算 stack 內所有大樓 也作為左端點

    ans = 0
    stk = []  # 單調遞增 stack 存 pi
    append, pop = stk.append, stk.pop  # 快取函數
    pi, pv = -1, 0  # pi 快取 stack 最後一項, pv 為 sentinel
    for i, v in enumerate(l):
        while pv > v:  # 結算所有比當前高的點
            pi = pop()  # 取前一個矮樓 當左端點
            # 計算面積 = 高度pv * 寬度(i-1) - pi
            pv *= i + ~pi  # pi *= i - pi - 1
            if pv > ans: ans = pv  # 更新最大面積
            pv = l[pi]  # 取前一個矮樓的高度
        if pv == v:  # 高度相同 直接取代 pi 即可 (作為其他高樓左端點要取 right most)
            pi = i
        else:  # pv < v 新增高樓到 stack
            append(pi)
            pi, pv = i, v
    print(ans)
main()

### [P-6-1. 小朋友上樓梯最小成本](https://judge.tcirc.tw/problem/d066)

注意到每次的轉移只跟前兩項有關，因此只要用兩個變數表示前置狀態即可，不用存一整個 DP 表。

善用 Python 的 tuple unpacking 賦值，這種線性轉移的題目都可以寫得很簡潔。

$Time: O(1), Space: O(1)$

def main():
    from sys import stdin
    e = stdin.readline

    e()
    l = map(int, e().split())

    d = p = 0
    for v in l:
        # dp[i] = min(dp[i-2], dp[i-1]) + l[i]
        d, p = p, min(d, p) + v
    print(p)
main()

### [P-6-2. 不連續的表演酬勞](https://judge.tcirc.tw/problem/d067)

$Time: O(1), Space: O(1)$

def main():
    from sys import stdin
    e = stdin.readline

    e()
    l = map(int, e().split())

    d = p = 0
    for v in l:
        # dp[i] = max(dp[i-2] + l[i], dp[i-1])
        d, p = p, max(d + v, p)
    print(p)
main()

### [P-6-3. 最小監控鄰居的成本](https://judge.tcirc.tw/problem/d068)

注意到 DP 狀態初始化的部分，前幾題都是一律設成 $0$，因為在開始之前成本、酬勞都是 $0$，這很直覺。
但這題卻是 $0, 0, \inf$，為啥是 $\inf$？回歸 DP 的狀態定義：`dp[i]` 表示「選擇 `i` 點，且 `<= i+1` 的點都已被監控」，假設使用 1-based 編號，`-1` 以及以前的點不需要監控，因此可以視為已監控，而 `dp[-1]` 會監控到 `-1`，所以 `dp[i] = 0 for i <= -1`，也因此程式中的 `dp0, dp1` 都初始化為 $0$。
而 `dp[0]` 會監控到 `1`，但這點不可能存在，為了表示這個「不可能」的概念，我們可以設計他的值，使他在後續的 DP 中「不可能」轉移，因為要求最小值，因此將他設定為 $\inf$ 即可。

吳邦一教授講義中的題目設定 $n \ge 3$，因此前 $3$ 項可以直接從給定的數列計算，不需要考慮這種 edge case，但 Judge 上的版本沒有特別這樣規定，因此若不特判 $n \lt 3$ 的情況，或用上述方法，就會在初始化階段吃 `IndexError`。

最後，別忘了 `dp[n]` 和 `dp[n-1]` 都可以監控到 `n` 以前的所有點。

$Time: O(1), Space: O(1)$

def main():
    from sys import stdin
    e = stdin.readline

    e()
    l = map(int, e().split())

    dp0, dp1, dp2 = 0, 0, float("INF")
    for v in l:
        # dp[i] = min(dp[i-3], dp[i-2], dp[i-1]) + l[i]
        dp0, dp1, dp2 = dp1, dp2, min(dp0, dp1, dp2) + v
    print(min(dp1, dp2))
main()

### [P-6-6. 方格棋盤路線](https://judge.tcirc.tw/problem/d069)

這題可以用「滾動 DP」的技巧達到 $O(2n)$ 空間複雜度，但仔細一點會發現可以 $O(1n)$。

使用 `le`, `ri` 兩個變數減少列表操作，DP 的壓常方式就是這麼單純，但實作起來很好玩。

第一行可以直接做前綴和，跑比較快。

$Time: O(mn), Space: O(n)$

def main():
    from sys import stdin
    from itertools import accumulate
    e = stdin.readline
    imp = float("-INF")

    m, n = map(int, e().split())
    # 第一行直接做前綴和就好
    dp = list(accumulate(map(int, e().split())))
    for _ in range(m - 1):  # 還有 m - 1 行要 DP
        le = imp  # 不可能從棋盤外轉移
        for i, (v, up) in enumerate(zip(map(int, e().split()), dp)):
            # dp[i][j] = max(dp[i][j-1] + dp[i-1][j]) + l[i][j]
            le = dp[i] = max(le, up) + v
    print(dp[-1])
main()

### [P-6-7. LCS](https://judge.tcirc.tw/problem/d070)

這一題同樣也可以只開單倍空間。
`ul` 是指左上角的格子，可以琢磨一下各變數之間的傳遞順序及關係。

這題最後可以直接輸出 `le`，前一題卻得 `dp[-1]`，因為前一題的第一行用前綴和優化掉了，在 $m = 1$ 的情況下 `le` 不存在而最終報錯。

$Time: O(mn), Space: O(\min(m, n))$

def main():
    from sys import stdin
    e = stdin.readline

    a, b = e().strip(), e().strip()
    m, n = len(a), len(b)
    # 以較短的字串開空間
    if m < n: a, b, m, n = b, a, n, m
    dp = [0] * n
    for x in a:
        le = ul = 0
        for i, (y, up) in enumerate(zip(b, dp)):
            # dp[i][j] = dp[i-1][j-1] + 1 if a[i] == b[j]
            #            else max(dp[i-1][j], dp[i][j-1])
            le = dp[i] = ul + 1 if x == y else max(up, le)
            ul = up
    print(le)
main()

### [P-6-9. 大賣場免費大搬家](https://judge.tcirc.tw/problem/d071)

經典的 0-1 背包問題。

這類題目是「由重量小轉移向重量大」，因此只要「由重量大往重量小更新」就可以只用一倍空間，但倒序更新的 index 不好寫，那乾脆把整個 DP 表倒過來，就可以直接順序更新了。
如果寫成「由重量小往重量大更新」的話，就會把同一輪的轉移重複累積，就壞掉了。

`False` 也可以全部初始化為 $-\inf$，然後拿掉條件判斷；或者用一個變數累積重量，每次從重量總和開始轉移。
但不能使用 `None`，否則 `x > dp[i]` 會 `TypeError`；也不能使用 `True`，因為 `True == 1`，而 `False == 0`。順帶一提，Python 的 `bool` 是 `int` 的子類。

$Time: O(nw), Space: O(w)$

def main():
    from sys import stdin
    e = stdin.readline

    n, k = map(int, e().split())
    ws = map(int, e().split())
    vs = map(int, e().split())
    k += 1  # 轉成開區間

    ans = 0
    # 紀錄 w ∈ [0, k] 的最大價值
    # dp[~i] = 重量為i的最大價值
    dp = [False] * k
    dp[~0] = 0
    for w, v in zip(ws, vs):
        if w >= k: continue  # 本來就超過k
        # 由 dp[j] 轉移向 dp[i]
        # dp[i] = max(dp[i], dp[i - w] + v)
        for i, j in enumerate(range(w, k)):
            x = dp[j]
            if x is False: continue  # 空格子 跳過
            x += v
            if x > dp[i]:
                dp[i] = x
                if x > ans: ans = x
    print(ans)
main()

### [Q-6-4. 闖關二選一](https://judge.tcirc.tw/problem/d072)

交替著轉移，總共有四種轉移方式，善用 tuple unpacking 語法可以寫得很漂亮。

$Time: O(n), Space: O(1)$

def main():
    from sys import stdin

    n, t = map(int, stdin.readline().split())
    pa = pb = t  # 初始位置

    d = p = 0  # 每一輪走左, 右邊的最小成本
    for e in stdin:
        a, b = map(int, e.split())  # 下一個關卡的兩個位置
        # 轉移 O(4)
        # dp[i][0] = min(dp[i - 1][0] + abs(l[i - 1][0] - l[i][0]), 
        #                dp[i - 1][1] + abs(l[i - 1][1] - l[i][0]))
        # dp[i][1] = min(dp[i - 1][0] + abs(l[i - 1][0] - l[i][1]), 
        #                dp[i - 1][1] + abs(l[i - 1][1] - l[i][1]))
        d, p = min(d + abs(pa - a), p + abs(pb - a)), \
               min(d + abs(pa - b), p + abs(pb - b))
        pa, pb = a, b
    print(min(d, p))
main()

### [Q-6-5. 二維最大子矩陣](https://judge.tcirc.tw/problem/d073)

其實就是 [Q-2-12-最接近的子矩陣和](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part1#Q-2-12-最接近的子矩陣和) 的簡易版，甚至我在那題就有用到這題的解作剪枝了。

在 TCIRC judge 上，一般的解法 Python 可能過不了，下面是一個加上了剪枝的解，在 TCIRC judge 上竟有奇效（但有額外開銷，換個測資可能就慢了）。

每一橫行由左而右做前綴和，同時計算原數列的最大子區間和，再將每一橫行的最大區間和於直向由上到下做前綴和，如此一來任兩項相減算出的區間就會是「某一個直向區間內，所有橫向數列的最大子區間和」，條件非常寬鬆，但剛好在 Judge 測資內可以剪掉很多枝。實際執行剪枝的部分在第 `29` 行。

$Time: O(mn^2), Space: O(mn)$

def main():
    from sys import stdin
    e = stdin.readline

    m, n = map(int, e().split())

    pre = [[0] * (n + 1) for i in range(m)]
    # 針對每一行做 最大子序列和 再加工成前綴和
    pre_ub = 0
    ub = [0] * m
    for i, pre_row in enumerate(pre):
        dp = res = pre_pre = 0
        for j, val in enumerate(map(int, e().split())):
            pre_pre = pre_row[j] = pre_pre + val  # 矩陣每行做前綴和
            dp += val
            if dp > res: res = dp
            elif dp < 0: dp = 0
        pre_ub = ub[i] = pre_ub + res  # 加工成前綴和

    ans = 0
    uub = ub[-1]
    for s in range(n):
        for t in range(s, n):
            dp = 0
            for row, cub in zip(pre, ub):
                dp += row[t] - row[s-1]
                if dp > ans: ans = dp
                elif dp < 0: dp = 0
                if dp + uub - cub <= ans: break  # 剪枝
    print(ans)
main()

### [Q-6-8. Local alignment](https://judge.tcirc.tw/problem/d074)

就是轉移邊上帶權的 LCS，只是因為有負權轉移，所以答案不能直接取右下角，而是要對所有格子取 $\max$。

推個自己出的類題：[Bob 的答案卡（Answer Sheet）](https://hackmd.io/@apcs-simulation-/SJQcOFrNel)，可以到 [APCSS Judge](https://apcs-simulation.com/problem/apcs1804_py) 上測試。

$Time: O(mn), Space: O(\min(m, n))$

def main():
    from sys import stdin
    e = stdin.readline

    a, b = e().strip(), e().strip()
    m, n = len(a), len(b)
    if m < n: a, b, m, n = b, a, n, m

    ans = 0
    dp = [0] * n
    for x in a:
        le = ul = 0
        for i, (y, up) in enumerate(zip(b, dp)):
            # dp[i][j] = dp[i-1][j-1] + 8 if a[i] == b[j]
            #            else max(0, dp[i-1][j] - 3, dp[i][j-1] - 3, dp[i-1][j-1] - 5)
            le = dp[i] = ul + 8 if x == y else max(0, up - 3, le - 3, ul - 5)
            if le > ans: ans = le  # 答案對每個格子取 max
            ul = up if up > 0 else 0
    print(ans)
main()

### [Q-6-10. 置物櫃出租](https://judge.tcirc.tw/problem/d075)

在上一篇的 [Q-1-8. 子集合的和](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part1#Q-1-8-%E5%AD%90%E9%9B%86%E5%90%88%E7%9A%84%E5%92%8C) 就有提到這種解法。

$Time: O(n), Space: O(n)$（不負責任地將位元運算全視為 $O(1)$）

def main():
    from sys import stdin
    e = stdin.readline

    # 人數(用不到) 櫃子總數 櫃子需求量
    n, m, s = map(int, e().split())
    l = tuple(map(int, e().split()))

    m -= sum(l)  # 沒有被借走的櫃子
    if m >= s:
        # 剩下的櫃子夠用 不用退還
        print(0)
    else:
        bit = 1
        for i in l:
            bit |= (bit << i)
        # 把剩下的櫃子都先借出
        # 至少需要退還 s-m 個
        s -= m
        bit >>= s
        # 找出最右邊的1 (lowbit(x) = x & -x)
        print(s + (bit & -bit).bit_length() - 1)
main()

### [P-6-11. Catalan number](https://judge.tcirc.tw/problem/d076)

Catalan number 是組合學內特別有意思的一個數，

照題意的轉移式，但 Bottom-up。只要按照 $1 \sim n$ 的方式求值即可。

$Times: O(n^2), Space: O(n)$

n = int(input())
p = 1000000009
c = [None] * (n+1)
c[0] = 1
for x in range(1, n+1):
    c[x] = sum(c[i] * c[x-i-1] % p for i in range(x)) % p
print(c[n])

使用 Catalan number 的另一個意義：在 $n \times n$ 方格上走捷徑，且**不越過對角線**的方法數。二維方格紀錄一維就足夠轉移了。

因為不需要做乘法，會快一些。

$Times: O(n^2), Space: O(n)$

n = int(input())
p = 1000000009
c = [0] * n
for x in range(1, n + 1):
    pre = 1
    for i in range(x):
        pre = c[i] = (c[i] + pre) % p
print(pre)

根據以上走方格的性質，能夠輕易推導出公式，可以參考 [這篇](https://johnmayhk.wordpress.com/2014/02/03/cn/)，寫得很明瞭。

數學解，代公式 $\frac{1}{n+1}\binom{2n}{n} = \frac{(n+2) \times (n+3) \times ... \times (2n)}{n!}$，使用費馬小定理對分母取乘法反元素。

$Times: O(n + \log_2 p), Space: O(1)$

def main():
    from sys import stdin
    p = 1000000009
    n = int(stdin.readline())
    ans = 1
    for i in range(2, n + 1):  # 分母 1*2*...*n
        ans = ans * i % p
    ans = pow(ans, -1, p)  # 取倒數變成分母
    for i in range(n + 2, n << 1 | 1):  # 分子 n+2*n+3*...*2n
        ans = ans * i % p
    print(ans)
main()

除此之外，卡塔蘭數還能推廣到高維度，跟「楊表」扯上關係，也可以說楊表就是「高維卡塔蘭數」，有興趣的話來試試看我出的 [太簡單的石板（Easy-peasy Puzzel）](https://hackmd.io/@apcs-simulation-/SkH6915l1e)，可以到 [APCSS Judge](https://apcs-simulation.com/problem/apcs1103) 上測試。順帶一提，這題在模擬賽中滅台，首殺耗時 $970$ 小時 $30$ 分 $21$ 秒，目前除了我以外只有一個人寫出來（但我不知道怎麼證明這題的解法是對的，所以這題算是出爛了QAQ）。

### [P-6-13. 周伯通的基地台](https://judge.tcirc.tw/problem/d077)

不需要將所有 DP 值存起來，只需要留著長度最多 $2k + 1$ 的單調遞增 `deque` 用於狀態轉移即可。

$Time: O(n), Space: O(k)$

def main():
    from sys import stdin
    from collections import deque
    e = stdin.readline

    n, k = map(int, e().split())
    r = k * 2 + 1  # 基地台可覆蓋範圍
    k += 1  # 轉成開區間 方便後面的範圍判斷

    ans = float("INF")
    # 單調遞增 deque[tuple[int, int]]
    q = deque(maxlen=r)
    for i, v in enumerate(map(int, e().split())):
        # 剔除過左的基地台 (覆蓋範圍與目前的基地台結合無效)
        if i > r:
            le = i - r
            while q[0][0] < le:
                q.popleft()

        # 第 k+2 個基地台開始無法覆蓋到最左端 要加上前面的基地台
        if i > k:
            v += q[0][1]

        if i + k < n:
            # 加入目前的基地台並維護單調遞增
            while q and q[-1][1] >= v:
                q.pop()
            q.append((i, v))
        else:
            # 基地台已經覆蓋到最右端 直接更新答案
            if v < ans: ans = v
    print(ans)
main()

### [P-6-15. 一覽衆山小](https://judge.tcirc.tw/problem/d078)

經典 LIS 裸題。

初始化直接取第一項即可，也不用塞 sentinel；二分搜前，可以先特判是否增加 LIS 長度，在數列遞增的情況下可以達到 $O(n)$ 複雜度。

$Time: O(n \log_2 n), Space: O(n)$

def main():
    from sys import stdin
    from bisect import bisect_left
    e = stdin.readline

    n = int(e())
    l = map(int, e().split())

    lis = [next(l)]  # 取第一項做初始化
    for i in l:
        if i > lis[-1]:  # 特判: 增加 LIS 長度
            lis.append(i)
        else:  # 二分搜
            lis[bisect_left(lis, i)] = i
    print(len(lis))
main()

### [P-6-16. 山寨華山論劍](https://judge.tcirc.tw/problem/d118)

這題不知道為甚麼跑到中一中題單上的最後，我這裡特判一下把他拉回來哈。

DP 經典題，解法不贅述。

為了節省空間，將 DP 值直接放進 `l` 內，因為 `l[i]` 不會再用到。記得要設定 `hi=i` 不然會出問題。
需要注意的是 `bisect` 在 APCS 用的 Python 3.6 還沒有 `key`，所以要改成直接用 `tuple` 下去二分搜：

w += l[bisect_left(l, (s, ), hi=i) - 1][1]

因為我把用於比較的數值放在 index 0 所以影響不大，只是 `tuple` 的比較會稍慢。

$Time: O(\text{sort} + n \log_2 n), Space: O(n)$

def main():
    from sys import stdin
    from bisect import bisect_left
    from operator import itemgetter
    e = stdin.readline

    n = int(e())
    # 按照結束時間升冪排列
    l = sorted((tuple(map(int, e().split())) for _ in range(n)), key=itemgetter(1))
    end0 = l[0][1]  # 最早結束時間 轉移的最低門檻

    ans = 0
    # 直接在l上dp
    for i, (s, t, w) in enumerate(l):
        if s > end0:  # 前面有可以轉移的點
            # 二分搜 結束時間 < 起始時間的rightmost
            w += l[bisect_left(l, s, hi=i, key=itemgetter(0)) - 1][1]
        if w > ans: ans = w  # 更新答案?
        l[i] = (t, ans)  # 將目前的dp值寫入l 結束時間用於二分搜
    print(ans)
main()

### [P-6-17. 切棍子](https://judge.tcirc.tw/problem/d079)

一般的區間 DP，以下是 bottom-up 的版本，從短區間算到長區間即可。

$Time: O(n^3), Space: O(n^2)$

def main():
    from sys import stdin
    e = stdin.readline

    n, l = map(int, e().split())
    # 加上頭尾兩個端點
    n += 2
    l = (0, *map(int, e().split()), l)

    # dp[j][i] = [i, j)區間的解
    dp = tuple([0] * i for i in range(n))
    for r in range(2, n):
        for i in range(n - r):
            j = i + r
            dp[j][i] = l[j] - l[i] + min(dp[k][i] + dp[j][k]
                                         for k in range(i + 1, j))
    print(dp[-1][0])
main()

### [P-6-19. 階梯數字](https://judge.tcirc.tw/problem/d080)

我的 [前一篇學習歷程](https://hackmd.io/@ericshen19555/APCS_optimized#:~:text=(ans)%0A%E2%80%8Bmain()-,%E9%9A%8E%E6%A2%AF%E6%95%B8%E5%AD%97,-%E9%80%99%E9%A1%8C%E6%98%AF) 也有收錄這題 APCS 考古題。

我直接解釋以下數學解，最差 $O(n)$，但實際上常數巨小，只有在「左側最大值 $\lt$ 當前數字」的時候需要做計算，因次計算次數的 worst case 是常數 $10$ 左右。

用數位 DP 的邏輯，從高位開始計算，每個位置計算「和 `num` 前綴相同的所有數字中，小於 `num` 的所有階梯數字」。
分三種狀況討論：數字減少、數字相等、數字增加，若是減少，則代表「和 `num` 前綴相同的所有數字中，已經沒有階梯數字了」，輸出答案；若是相等，則代表「和 `num` 前綴相同的所有數字中，沒有當前數位較小的階梯數字」，因為當前數位的數字減少以後就必定不是階梯數字，因此此數位不需要計算答案；若是增加，則是我們主要需要計算的 case，假設增加前的數字是 `last`，增加後（也就是當前數位）的數字是 `cur`，則「和 `num` 前綴相同的所有數字中」階梯數字的數量即為 $H(9 - last + 1, i) - H(9 - cur + 1, i)$，其中 $H$ 是排組中的**重複組合**，`i` 可以理解為剩餘未決定的數位有幾個，而 $H(9 - digit + 1, pos)$ 這個公式計算的是「剩餘數位中，填入 $0 \sim 9 - digit + 1$ 個上升點，從 $digit$ 上升到 $digit \sim 9$」的種類數，而因為有上限所以兩兩相減成區間。
以上論述只是極度粗淺大略的概念（我盡可能在詳細和可讀性之間權衡了qwq），實際上還牽涉到一些 $+1-1$ 的瑣碎問題，再加上這是數學排組題，因此要 debug 寫到正確真的挺煩的，建議可以 run 底下的 readible 版解法，他是多筆測資，並且運行時會視覺化計算，希望能幫助你理解 :)。

這樣的算法算的會是 $[0, num)$ 區間內的解（必計入 $0$ 這個「階梯數字」），然而題目要求的是 $[1, num]$ 區間，若 `num` 是階梯數字，和 $0$ 剛好 $+1-1$ 抵銷了；但在 `num` 本身不是階梯數字時，答案要 $-1$。

再觀察到每次計算兩個 $H$ 相減的時候，兩個 $H$ 之間的分子有部分重複，因此用分配律減少計算量。

分母因為只會有 $0 \sim 9$ 的反階乘，我就直接寫死了。

$Time: O(t \times n), Space: O(1)$

- readible 版

def main():
    from sys import stdin
    mod = 1000000007

    def dp(pos, digit):
        # dp(pos, digit) = H(9 - digit + 1, pos)
        res = rev_fac[~digit]
        for i in range(pos + 1, pos + 10 - digit):
            res *= i
        return res % mod

    # 0! ~ 9! 的模逆元
    rev_fac = (1, 1, 500000004, 166666668, 41666667, 808333339, 301388891, 900198419, 487524805, 831947206)

    for num in map(str.strip, stdin):
        ans = last = 0
        n = len(num)
        for i, cur in zip(range(n, 0, -1), map(int, num)):
            if cur < last:
                # num 本身不是階梯數字
                ans -= 1
                break
            if cur > last:
                # 遇到上升點 查值一次
                print("0" + num[:n-i] + "_" * i)
                print(f"{last} -> {cur} || {i = }")
                print(f"H({9 - last + 1}, {i}) - H({9 - cur + 1}, {i}) = {dp(i, last) - dp(i, cur)}")
                print()
                ans += dp(i, last) - dp(i, cur)
            last = cur
        print(ans % mod)
        print("---" * 10)
main()

- 分配律優化

def main():
    from sys import stdin
    mod = 1000000007

    # 0! ~ 9! 的模逆元
    rev_fac = (1, 1, 500000004, 166666668, 41666667, 808333339, 301388891, 900198419, 487524805, 831947206)

    num = stdin.readline().strip()
    ans = last = 0
    n = len(num)
    for i, cur in zip(range(n, 0, -1), map(int, num)):
        if cur < last:
            # num 本身不是階梯數字
            ans -= 1
            break
        if cur > last:
            # 遇到上升點 查值一次
            # 分兩段連乘
            a = 1
            if cur == 9:
                x = i
            else:
                for x in range(i + 1, i + 10 - cur):
                    a *= x
            b = 1
            for x in range(x + 1, i + 10 - last):
                b *= x
            # 分配律
            ans += a * (b * rev_fac[~last] - rev_fac[~cur]) % mod
        last = cur
    print(ans % mod)
main()

### [P-6-20. Hyper-cube path](https://judge.tcirc.tw/problem/d081)

在吳邦一教授的 Python 版講義中有補充 Bottom-up 的解法詳細說明。簡單來講，每個節點的編號增加一個 bit 以後會變成下一個狀態，反過來講，一個節點的前置狀態就是扣掉其中一個 bit。因此有兩種做法：枚舉下一個狀態並更新其值、枚舉前置狀態並由他轉移，而每個節點的前置狀態數量即是他的 bit count，根據 bit count 由小到大 BFS 即可。

這樣的解法無疑是好的，但可以做一些優化：
枚舉前或後狀態時當然可以枚舉每一位，再檢查是否可轉移，但其實可以直接篩選出可轉移的邊，以下面的程式碼（枚舉前置狀態）說明：首先將節點編號 `i` 複製給 `j`，每一次 `while` 迴圈就從 `j` 拿掉 `j` 的 low-bit，而 `i` 扣掉當下的這個 low-bit 就會是其中一個前置狀態；如果是要枚舉下一個狀態，就將節點編號先做一次位元翻轉就好了。這樣一來總轉移時間就從 $n \times 2 ^ n$ 減少到 $2 ^ n$（轉移總數，所有編號的 bit count 總和）。
至於遍歷順序，因為每個節點的前置狀態是扣掉任意一個 bit，所以節點編號的值也會大於所有其前置狀態，因此直接照節點編號由小到大遍歷即可。

$Time: O(2 ^ n), Space: O(2 ^ n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = 1 << int(e())  # 節點數
    l = list(map(int, e().split()))

    for i in range(n):  # Bottom-up
        j = i
        v = 0  # 子節點最大權
        while j:  # 找所有子節點
            lb = j & -j  # low-bit
            j -= lb
            x = l[i - lb]
            if x > v: v = x
        l[i] += v
    print(l[-1])
main()

### [P-6-21. 刪除邊界](https://judge.tcirc.tw/problem/d082)

同上篇的 [Q-1-11. 刪除矩形邊界](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part1#Q-1-11-%E5%88%AA%E9%99%A4%E7%9F%A9%E5%BD%A2%E9%82%8A%E7%95%8C)。

### [P-6-22. 文無第一武無第二](https://judge.tcirc.tw/problem/d083)

主要邏輯與講義內並無二致，只是加入了些許特判避免大開銷操作。而在維護戰力總和遞增的部分，原解是全部用 `pop`，我則是找出右端點 `j`（右開區間），再將整個區間一次刪除，不僅效率上快一些，右開區間也使 index 更加乾淨簡潔。

$Time: O(n ^ 2), Space: O(n)$

def main():
    from sys import stdin
    from bisect import bisect_right
    e = stdin.readline

    n = int(e())
    l = list(zip(map(int, e().split()), map(int, e().split()), map(int, e().split())))
    # 先c降序 再m升序 所求變成m單調遞增的最大p總和
    l.sort(key=lambda x: (-x[1], x[2]))

    dp = [(-1, 0)]  # list[tuple[m, p]] 以m結尾的最大戰力p總和
    for p, c, m in l:
        pm, pp = dp[-1]
        if pm == m:  # 特判 最後一個剛好m 可以直接加進去
            dp[-1] = (m, pp + p)
        elif pm < m:  # 特判 嚴格大於前面所有
            dp.append((m, pp + p))
        else:  # pm > m
            i = bisect_right(dp, (m, pp))
            pm, pp = dp[i-1]
            p += pp
            if pm == m:  # 特判 如果前一個剛好m 可以取代掉(等於直接加進去)
                i -= 1
            # 維護p總和嚴格遞增
            j = i
            while j < len(dp) and dp[j][1] <= p:
                j += 1
            if i < j:  # 如果有可以刪的 取代第一個 刪掉後面的
                dp[i] = (m, p)
                del dp[i+1:j]
            else:  # 沒有可以刪的 只能硬插
                dp.insert(i, (m, p))
    print(dp[-1][1])
main()

### [Q-6-12. 楊鐵心做 1 休 K](https://judge.tcirc.tw/problem/d084)

易知 `dp[i] = max(dp[:i-k])`，為了要達到 $O(1)$ 轉移與最優空間，使用一個長度為 $O(k)$ 的 deque 暫存中間無法轉移的部分，並用 `pre` 持續更新可轉移的最大值。

注意因為 deque 的長度為 $k$，`popleft` 的是 $k-1$ 天前的狀態，還不能轉移，要先轉移完再更新。

$Time: O(n), Space: O(k)$

def main():
    from sys import stdin
    from collections import deque
    from itertools import islice
    e = stdin.readline

    n, k = map(int, e().split())
    l = map(int, e().split())

    pre = 0  # k天前的最高獲利 (可轉移的部分)
    dp = deque(islice(l, k), maxlen=k)  # 前k天彼此無法轉移 直接存入
    for i in l:
        head = dp.popleft()  # k-1天前 這輪還不能從這轉移但先存著
        dp.append(i + pre)  # 從k天前轉移
        if head > pre: pre = head  # 維護最大獲利
    print(max(pre, max(dp)))
main()

### [Q-6-14. K 次買賣](https://judge.tcirc.tw/problem/d085)

下面的是標準的 DP 解，`x`, `y` 之間轉移關係的實作很漂亮但較不好理解，而且注意他們並不是用 tuple unpacking 達成同時轉移，`x =` 是從**上一輪** `for row in dp` 的迴圈中轉移完的 `y` 轉移，「上一輪迴圈到這一個迴圈」是 `dp[i-1]` 到 `dp[i]`，也就是在買入時「增加一次買賣次數」；而 `y =` 則是從**這一輪**迴圈的 `x` 轉移，因為題目說「允許當天買賣」。

悲傷的是這個解會 TLE。

$Time: O(n \times k), Space: O(k)$

def main():
    from sys import stdin
    e = stdin.readline

    n, k = map(int, e().split())
    l = map(int, e().split())

    inf = float("INF")
    dp = [[inf, 0] for i in range(k)]
    for v in l:
        x, y = inf, 0  # 初始化: 0次買賣 沒東西可以脫手 利潤為零
        for row in dp:
            x = row[0] = min(row[0], v - y)  # 減少買入成本: 維持原樣/改為此時買入?
            y = row[1] = max(row[1], v - x)  # 增加賣出利潤: 維持原樣/改為此時賣出?
    print(y)  # k次買賣後的最大利潤
main()

但別急著悲傷！這題有 $O(n \log_2 k)$ 甚至 $O(n)$ 的解法！此時 DP 已經不夠用了，得貪心！（以下解法參考了 [此 LeetCode 題解](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/solutions/54145/O\(n/)）

核心思想是「低買高賣、壓低交易次數」，因此對於一段連續上升的價格，最佳的買賣方式就是「最低點買、最高點賣」，中間則跳過，如此就產生了許多「山谷-山峰對」，以下簡稱 $\text{vp}$ (valley-peak)。理想情況下每一對 $\text{vp}$ 都做交易會有最大值，但因為 $k$ 次的限制，得要貪心地「忍痛割愛」，合併某些 $\text{vp}$，減少部分利潤以符合交易次數規定，首先因為我們找 $\text{vp}$ 的方式，假設兩對相鄰的 $\text{vp}$ 為 $(v_1, p_1), (v_2, p_2)$，則 $v_1 \lt p_1 \ge v_2 \lt p_2$，若是兩 $\text{vp}$ 為以下狀況：

        /p2
  p1/  /
   /  /v2
v1/

如果只能交易一次，與其兩次交易二選一，將兩組 $\text{vp}$ 合併成一個 $(v_1, p_2)$，利潤會更高！但我們怎麼知道交易次數夠不夠？又怎麼知道要合併哪兩組 $\text{vp}$、那些又要留著？如果通靈能力特好就會想到：若是把兩組 $\text{vp}$ **重疊的部分利潤**視為一組 $\text{vp}$，也就是將原本兩組都交易的利潤 $(p_1 - v_1) + (p_2 - v_2)$ 改寫成 $(p_2 - v_1) + (p_1 - v_2)$，前一組是合併後的 $\text{vp}$，如果交易次數不夠就貪心地取他，後一組的利潤必然較低，則取到後一組時前一組必已取，合起來就變成原本兩個 $\text{vp}$ 都取了！

為了要貪心地選取 $\text{vp}$ 做合併，可以維護單調性讓 $v$ 嚴格遞增，無法合併的 $\text{vp}$ 就直接結算交易利潤，而維護前 $k$ 筆最大的利潤可以用一個 min-heap，動態地剃除最小利潤。

空間的 worst case 為 `1 6 2 5 3 4` 這種，Stack 裡面會有 $n / 2$ 個 $\text{vp}$。

$Time: O(n \log_2 k), Space: O(n)$

def main():
    from sys import stdin
    from heapq import heappush, heappushpop
    e = stdin.readline

    n, k = map(int, e().split())
    l = map(int, e().split())

    q = []  # minheap for answer, maxlen=k
    vps = []  # stack[tuple[int, int]]: previous valley-peak pairs
    pv, pp = -1, float("INF")  # top of vps, initialize as sentinel
    cur, nxt = next(l), next(l, None)
    while nxt is not None:
        # find a valley-peak pair
        # next valley (until next > curr)
        while nxt is not None and nxt <= cur:
            cur, nxt = nxt, next(l, None)
        v = cur
        # next peak (until next < curr)
        while nxt is not None and nxt >= cur:
            cur, nxt = nxt, next(l, None)
        p = cur

        # skip valley-peak pairs that is meaningless to combine
        while pv >= v:
            # add profit to answer, keeping len(q) <= k
            (heappush if len(q) < k else heappushpop)(q, pp - pv)
            pv, pp = vps.pop()

        # try combine multiple valley-peak pairs
        while pp <= p:
            # add profit to answer, keeping len(q) <= k
            (heappush if len(q) < k else heappushpop)(q, pp - v)
            v = pv
            pv, pp = vps.pop()

        vps.append((pv, pp))
        pv, pp = v, p
    # add rest pairs
    vps.append((pv, pp))
    vps = iter(vps)
    next(vps)  # drop sentinel
    for v, p in vps:
        # add profit to answer, keeping len(q) <= k
        (heappush if len(q) < k else heappushpop)(q, p - v)

    print(sum(q))
main()

那 $O(n)$ 呢？要消掉 $\log_2 k$ 就不能用 heap，這題其實沒有「動態」維護最小值的需求，只要全部存起來再取最大的 $k$ 個就好，卻怎麼找最大 $k$ 個？排序？那甚至變成 $n \log_2 n$ 了。答案是用選擇演算法，理論複雜度為 $O(n)$，C++ 的話可以用內建的 `nth_element`，而 Python 則要手刻，想法是類似 Quick Sort，根據一個 $pivot$ 將整個區間分成 $\ge pivot$ 和 $\lt pivot$ 的兩半部，只需遞迴處理包含第 $k$ 元素的一半，若是每一次都能均勻切割區間就會是 $O(n)$，則 $pivot$ 就得找中位數，使用 median of medians 就能夠 $O(n)$ 找出中位數，雖然能保證最壞依舊是線性但整體常數超大。

下面的程式則是從維基百科上抄來了「實務上最快」的選擇演算法 Floyd–Rivest algorithm，對於大規模區間，根據區間的大小與目標 $k$ 的相對位置，利用統計方法估算出一個窄化的子區間，其中第 $k$ 個元素出現的概率極高。這樣的預測使得後續的遞迴操作能夠更精準地縮小搜尋範圍，從而在平均情況下實現 $O(n)$ 的運行效率，比傳統的 Quick Select 更穩定和高效。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n, k = map(int, e().split())
    l = map(int, e().split())

    ans = []  # answers
    vps = []  # stack[tuple[int, int]]: previous valley-peak pairs
    pv, pp = -1, float("INF")  # top of vps, initialize as sentinel
    cur, nxt = next(l), next(l, None)
    while nxt is not None:
        # find a valley-peak pair
        # next valley (until next > curr)
        while nxt is not None and nxt <= cur:
            cur, nxt = nxt, next(l, None)
        v = cur
        # next peak (until next < curr)
        while nxt is not None and nxt >= cur:
            cur, nxt = nxt, next(l, None)
        p = cur

        # skip valley-peak pairs that is meaningless to combine
        while pv >= v:
            ans.append(pp - pv)
            pv, pp = vps.pop()

        # try combine multiple valley-peak pairs
        while pp <= p:
            ans.append(pp - v)
            v = pv
            pv, pp = vps.pop()

        vps.append((pv, pp))
        pv, pp = v, p
    # add rest pairs
    vps.append((pv, pp))
    vps = iter(vps)
    next(vps)  # drop sentinel
    for v, p in vps:
        ans.append(p - v)

    if len(ans) <= k:
        print(sum(ans))
    else:
        from math import log, exp, copysign
        # Floyd–Rivest algorithm from WIKIPEDIA
        def select(le, ri):
            while ri > le:
                if ri - le > 600:
                    r = ri - le + 1
                    i = rk - le + 1
                    z = log(r)
                    s = 0.5 * exp(2 * z/3)
                    sd = copysign(0.5 * (z * s * (r - s) / r) ** 0.5, i - r/2)
                    _le = max(le, int(rk - i * s / r + sd))
                    _ri = min(ri, int(rk + (r - i) * s / r + sd))
                    select(_le, _ri)
                t = ans[rk]
                i, j = le, ri
                ans[le], ans[rk] = ans[rk], ans[le]
                if ans[ri] > t:
                    ans[ri], ans[le] = ans[le], ans[ri]
                while i < j:
                    ans[j], ans[i] = ans[i], ans[j]
                    i, j = i + 1, j - 1
                    while ans[i] < t:
                        i += 1
                    while ans[j] > t:
                        j -= 1
                if ans[le] == t:
                    ans[le], ans[j] = ans[j], ans[le]
                else:
                    j += 1
                    ans[j], ans[ri] = ans[ri], ans[j]
                if j <= rk:
                    le = j + 1
                if j >= rk:
                    ri = j - 1
        rk = len(ans) - k
        select(0, len(ans) - 1)
        print(sum(ans[~i] for i in range(k)))  # max k values
main()

### [Q-6-18. 矩陣乘法鏈](https://judge.tcirc.tw/problem/d086)

經典題，有傳說中的 $O(n \log_2 n)$ 解法，以下的解是直接從 [這份實作](https://github.com/junodeveloper/Hu-Shing) 的 C++ 程式碼翻譯過來的，將 1-based 的毒瘤寫法改成 0-based，並將空間開剛剛好。

細節我也不太清楚...大略來說是將題目轉化為多邊形分割成多個三角形的問題，再加上一些數學上的神奇魔法，最後用 priority queue 取最小花費。

有興趣可以自己讀論文：
Hu, TC; Shing, MT (1981). ["Computation of Matrix Chain Products, Part I, Part II"](http://i.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf) (PDF)

$Time: O(n \log_2 n), Space: O(n)$

def main():
    from sys import stdin
    from itertools import accumulate
    from heapq import heappush, heappop
    from operator import attrgetter
    e = stdin.readline
    u_v_low_of = attrgetter("u", "v", "low")

    class HArc:
        # faster lookup
        __slots__ = ("u", "v", "low", "mul", "base", "num", "den")

        def __init__(self, u, v):
            self.u, self.v = u, v
            wu, wv = w[u], w[v]
            self.low = u if wu < wv else v
            self.mul = mul = wu * wv
            self.base = cp[v] - cp[u] - mul

        @property
        def support(self):
            return self.num // self.den

        def __lt__(self, other):  # minheap -> maxheap
            return self.num * other.den > other.num * self.den

    def add_arc(cur, arc):
        heappush(pq[qid[cur]], arc)
        u, v, _ = u_v_low_of(arc)
        con[u].append(arc)
        con[v].append(arc)

    def remove_arc(cur):
        arc = heappop(pq[qid[cur]])
        u, v, _ = u_v_low_of(arc)
        con[u].pop()
        con[v].pop()

    def get_mn_mul(node):
        if node == 0: return w[0] * (w[1] + w[n - 1])
        u, v, low = u_v_low_of(h[node])
        con_low = con[low]
        if con_low:
            con_low_top = con_low[-1]
            if u <= con_low_top.u and con_low_top.v <= v:
                return con_low_top.mul
        return w[low] * w[low + (1 if u is low else -1)]

    def merge_pq(node):
        child_node = child[node]
        max_child = max(child_node, key=sub_get)
        qid[node] = qid[max_child]
        cur_pq = pq[qid[node]]
        for i in child_node:
            if i == max_child: continue
            child_pq = pq[qid[i]]
            for arc in child_pq:
                heappush(cur_pq, arc)

    def dfs(node):
        nonlocal n_pqs

        cur = h[node]
        sub[node] = 0
        cur.den = cur.base
        if not child[node]:
            qid[node] = n_pqs
            n_pqs += 1
            cur.num = w[cur.low] * (cur.den + cur.mul - get_mn_mul(node))
            add_arc(node, cur)
            return

        for i in child[node]:
            dfs(i)
            sub[node] += sub[i]
            cur.den -= h[i].base

        w_low, mul = w[cur.low], cur.mul
        cur.num = w_low * (cur.den + mul - get_mn_mul(node))
        merge_pq(node)
        cur_pq = pq[qid[node]]
        while cur_pq:
            arc = cur_pq[0]
            if arc.support < w_low: break
            cur.den += arc.den
            remove_arc(node)
            cur.num = w_low * (cur.den + mul - get_mn_mul(node))
        while cur_pq:
            arc = cur_pq[0]
            if cur < arc: break
            cur.den += arc.den
            remove_arc(node)
            cur.num += arc.num
        add_arc(node, cur)

    n = int(e()) + 1
    l = tuple(map(int, e().split()))

    # init
    n_pqs = 0
    m = n + 1
    con = [[] for i in range(m)]
    child = [[] for i in range(m)]
    pq = [[] for i in range(m)]
    qid, sub = [0] * m, [0] * m
    sub_get = sub.__getitem__

    # input prepare
    mv, mi = min((v, i) for i, v in enumerate(l))
    w = [*l[mi:], *l[:mi], mv]
    cp = (0, *accumulate(w[i] * w[i + 1] for i in range(n)))

    # one_sweep
    stk, lst = [], []
    for i in range(n):
        while len(stk) >= 2 and w[stk[-1]] > w[i]:
            x = stk[-2]
            if x != 0 and i != 0:
                lst.append((x, i))
            stk.pop()
        stk.append(i)

    # build_tree
    stk = []
    top = 0
    h = [HArc(0, n)]
    for i, (u, v) in enumerate(lst, start=1):
        h.append(HArc(u, v))
        while u <= h[top].u and h[top].v <= v:
            child[i].append(top)
            top = stk.pop()
        stk.append(top)
        top = i
    root = child[0]
    root.append(top)
    root.extend(reversed(stk))
    root.pop()

    # get_ans
    dfs(0)
    cur_pq = pq[qid[0]]
    print(sum(map(attrgetter("num"), cur_pq)))

main()

### [Q-6-23. 直升機抓寶](https://judge.tcirc.tw/problem/d087)

這題實作不難，就是要想出好解法不簡單。

理想情況下，當然是每一行的寶物都抓得到，但是如果「後區間的右端點」在「前區間的左端點」左側（如下圖），就必須取捨，而較左的區間比較右的區間有更多潛力，所以應該要將前區間替換為後區間，很類似 LIS 的邏輯，LIS 其實就是這題將所有區間長度改為 $1$，邏輯是「刪除右邊最接近的數，插入此數」，而改成區間就變成「刪除右端點右邊最接近的區間，插入左端點（用於給後面的右端點做判斷）」。

後區間:  ###
前區間:       ###

以下實作是手刻一個簡易的 SortedList，註解是 $O(n)$ 暴力做的版本，方便理解邏輯。

$Time: O(n \sqrt n), Space: O(n)$

def main():
    from sys import stdin
    from bisect import bisect, insort
    e = stdin.readline
    # sorted list區塊最大長度
    load = 1000

    ans = n = int(e())  # 答案初始化 假設全部都能經過
    # 實作一個簡單的分塊sorted list
    sl, mx = [[-1]], [-1]
    for _ in range(n):
        s, t = map(int, e().split())
        # 使用差分的概念 維護每次dp數值的上升點
        if t < mx[-1]:
            # 如果前面有較後開始的區間 替換掉
            # sl.pop(bisect_right(sl, t))
            ans -= 1  # 必須取捨 答案-1
            i = bisect(mx, t)
            chunk = sl[i]
            j = bisect(chunk, t)
            chunk.pop(j)
            if not chunk:
                sl.pop(i)
                mx.pop(i)
            else:
                mx[i] = chunk[-1]
        # 插入新差分區間
        # insort(sl, s)
        if s >= mx[-1]:
            i = len(sl) - 1
            chunk = sl[i]
            chunk.append(s)
            mx[i] = s
        else:
            i = bisect(mx, s)
            chunk = sl[i]
            insort(chunk, s)
            mx[i] = chunk[-1]
        if len(chunk) >= load:
            idx = len(chunk) >> 1
            half = chunk[idx:]
            del chunk[idx:]
            sl.insert(i + 1, half)
            mx.insert(i, chunk[-1])
    print(ans)
main()

觀察到：`sl` 紀錄的「左端點」其實是類似「答案數值上升點」的概念，其實是離散地在維護一個差分序列，但需要二分搜下一個最接近的點，因此需求變成「能二分搜的前綴和」，老朋友 BIT 表示這我熟啊！在 BIT 上二分搜最直覺是 $O(\log_2 n)$ 求前綴和乘上 $O(\log_2 n)$ 二分搜，變成 $O((\log_2 n) ^ 2)$，但其實可以 $O(\log_2 n)$！純文字敘述不好理解，建議閱讀 [這篇文章](https://hackmd.io/@LittlePants/BJKNxEU6s#BIT%E4%B8%8A%E4%BA%8C%E5%88%86)，寫得詳細、圖很清晰。

因為題目的區間範圍都在 $2.5e5$ 以內，所以不需要離散化。

儘管理論複雜度較上解好上一截，但常數大反而跑很慢。

$Time: O(n \log_2 n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    high_bit = 1 << n.bit_length() - 1  # 最長區間位置 二分搜起始點
    bit = [0] * (n + 1)
    ans = 0
    for _ in range(n):
        s, t = map(int, e().split())

        # 找到二分搜目標值 sum+1是因為要bisect_right
        # target = sum(bit[:t+1]) + 1
        target = 1  # 先加上 1
        i = t + 1  # 1-based
        while i > 0:
            target += bit[i]
            i -= i & -i
        if target <= ans:
            ans -= 1  # 需要取捨

            # BIT上二分搜
            # i = bisect_right(bit, target)
            i = cur = 0
            di = high_bit  # 由最長區間開始二分搜
            while di > 0:
                ni = i + di
                if ni <= n:
                    nv = cur + bit[ni]
                    if nv < target:
                        i, cur = ni, nv
                di >>= 1  # 區間長度減半
            i += 1  # "先找到小於 k 的最後一個位置，然後再 +1"

            # 刪除區間左端點
            # bit[i] -= 1
            while i <= n:
                bit[i] -= 1
                i += i & -i

        # 新增區間左端點
        # bit[s] += 1
        i = s + 1  # 1-based
        while i <= n:
            bit[i] += 1
            i += i & -i
        ans += 1
    print(ans)
main()

<span id="088"></span>

### [Q-6-24. 隔離採礦](https://judge.tcirc.tw/problem/d088)

這題的最佳解是搭配單調棧進行 DP（我反而想不到 $O(n \log_2 n)$ 解 :P）。

每個點紀錄兩個狀態：不選取此點（作為支撐點）、選取此點，作為支撐的意思就是找左邊比自己矮的最大權點，若是從「選取」轉移到「支撐」比較直覺，而從「支撐」轉移到「支撐」則是「取代舊支撐點」的概念。為了計算哪些狀態可以轉移，可以用一個單調棧維護高度，找出左側較矮的點們。

這題的重點在於「等高點」只能從「支撐點」狀態轉移，而且轉移後必須刪除，因為還需要從「更高點」的「支撐點」狀態轉移，所以才說此題維護的單調棧須為嚴格遞減。這也是先前提過的：在單調棧題目中「等高點」的 case 需要特別注意的原因，若是這題少考慮了等高情況就會 WA。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    H = map(int, e().split())
    V = map(int, e().split())

    ans = 0
    # 嚴格下降的高度 (高度, 不選此點(作為支撐), 選取此點)
    stk = []
    pop, append = stk.pop, stk.append  # 快取 stk 函式
    ph, ps, pv = float("INF"), 0, 0  # stk 的最後一項 初始化為sentinel
    for h, v in zip(H, V):
        s = dp = 0  # s: 此點作為支撐, dp: 選取此點
        while ph < h:
            # 對於比較低的點 可以從 作為支撐/選取 兩種狀態轉移
            s = max(s, ps, pv)
            ph, ps, pv = pop()
        if ph == h:
            # 對於一樣高的點 只能從 作為支撐 轉移
            if ps > s: s = ps
            # 存入stk中的時候 選取此點 的狀態取大(高度一樣 所以等價)
            dp = pv
            # 以此點取代舊等高點
            ph, ps, pv = pop()
        # 對於比較高的點 只能從 作為支撐 的狀態轉移
        v += ps
        if v > dp: dp = v
        # 更新答案
        if dp > ans: ans = dp
        # 儲存此點資訊
        append((ph, ps, pv))
        ph, pv = h, dp
        if s > ps: ps = s
    print(ans)
main()

### [Q-6-25. 貨郎問題](https://judge.tcirc.tw/problem/d089)

經典 NP-hard 問題 TSP (Travelling salesman problem)，以下的解法中先使用了貪心解，枚舉從各節點出發，每次選最近的未造訪節點走，時間複雜度 $O(n ^ 3)$，得出來的答案用於後面 DP 時將過大的答案剪枝。

枚舉未造訪節點時使用 lowbit $O(1)$ 找出最小的 bit，比一位位枚舉快。

$Time: O(n ^ 2 \times 2 ^ n), Space: O(n \times 2 ^ n)$

def main():
    from sys import stdin
    e = stdin.readline
    inf = float("INF")

    n, _ = map(int, e().split())  # 從哪裡出發不重要
    every = (1 << n) - 1
    l = tuple(tuple(map(int, e().split())) for _ in range(n))

    ans = inf

    # 先貪心出大概的解 讓後面剪枝
    # 策略: 嘗試所有節點為起點 每次走向當前最近鄰居 O(n³) O(1)
    for i in range(n):
        s = i
        dis = 0
        bit = bit_ = every - (1 << i)
        while bit:
            l_i = l[i]
            nxt = (inf, -1)
            while bit_:  # 找尚未造訪的最近鄰居
                lowbit = bit_ & -bit_
                bit_ -= lowbit
                j = lowbit.bit_length() - 1
                nxt = min(nxt, (l_i[j], j))
            dis_, i = nxt
            dis += dis_
            if dis >= ans: break  # 剪枝
        else:
            ans = min(ans, dis + l[i][s])

    cur, nxt = {(every - 1, 0):0}, {}
    while cur:
        nxt.clear()
        for (bit, i), dis in cur.items():
            l_i = l[i]
            bit_ = bit
            while bit_:
                # 遍歷還沒到過的城市
                lowbit = bit_ & -bit_
                bit_ -= lowbit
                j = lowbit.bit_length() - 1
                dis_ = dis + l_i[j]
                if dis_ >= ans: break  # 剪枝
                if bit == lowbit:
                    # 走完這步就全部經過了 回到原點 更新答案
                    dis_ += l[j][0]
                    if dis_ < ans: ans = dis_
                else:
                    # 找找看是否有相同的狀態: 經過的城市們相同 最後一點相同
                    key = (bit - lowbit, j)
                    val = nxt.get(key, None)
                    # 未到過 或 路徑更短
                    if val is None or dis_ < val:
                        nxt[key] = dis_
        cur, nxt = nxt, cur
    print(ans)
main()

### [P-7-1. 探索距離](https://judge.tcirc.tw/problem/d090)

就是一般的有向圖 BFS。

前一題的解法就用到類似的 BFS 邏輯，在 [上篇](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part1#P-3-1-%E6%A8%B9%E7%9A%84%E9%AB%98%E5%BA%A6%E8%88%87%E6%A0%B9) 中也有提到這種 BFS 實作方法。

> 一般的 BFS 實作為了避免 `list.pop(0)` 這種燒雞寫法主要有兩種方式：使用 `collections.deque` 雙向佇列的 `deque.popleft`，他的複雜度是 $O(1)$；或者直接不從左邊移除元素，單純用一個指標指向當前遍歷到的地方，雖然感覺空間會燒雞，但仔細一想時間空間都是 $O(n)$，因此不會有問題，但總歸是浪費了空間。
以下這種 BFS 則是我很喜歡的一種實作方式（而且是原創），在兩種解法中間取了個折衷，避免了連續進行 `pop` 這種常數大的列表操作，又不會保留所有已經遍歷完的節點，最讚的是他可以同時維護當前的遍歷層數。

`G: list[list[int]]` 中原本儲存是某節點的所有子節點，可以將這個串列重複利用，用於紀錄是否已經遍歷過，我通常喜歡設成 `None`，因為可以用 `is` 來判斷，比較快也比較可靠，若是哪個地方忘記判到，`for ... in None` 也會 `TypeError`，能夠輕鬆 debug。只是要在標記成 `None` 之前把原先的子節點們存給用於 BFS 的串列，不然 `G[j] = None` 後原本的值會被直接丟掉。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n, m = map(int, e().split())
    s = int(e())

    G = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, e().split())
        if a != b:  # "邊的起點與終點未必不同"
            G[a].append(b)

    cnt = dis = 0  # 所求
    step = 1  # 當前步數
    cur = [G[s]]
    G[s] = None  # 走過作記號
    while cur:  # bfs
        nxt = []
        for ci in cur:
            for j in ci:
                cj = G[j]
                if cj is None: continue
                G[j] = None  # 走過作記號
                nxt.append(cj)
                cnt += 1
                dis += step
        cur = nxt
        step += 1
    print(cnt, dis, sep="\n")
main()

### [P-7-2. 開車蒐集寶物](https://judge.tcirc.tw/problem/d091)

找出最大權連通塊。

如果要用 BFS 或 DFS 一個個遍歷找出所有邊，就必須將所有邊先輸入、建鄰接表才能一個個遍歷，空間複雜度 $O(n + m)$，能不能省？

使用 DSU 就可以在線（on-line）地更新連通資訊，就不需要一次獨入所有邊了！

達到理論複雜度的 DSU 必須具備「路徑壓縮」和「按秩合併」，前者是查詢一次後就把查詢路徑上所有的節點都直接指向塊的父節點，使均攤查詢時間達到 $O(\alpha(n))$；後者則是將小塊合併至大塊，確保樹高的增長速度在 $\log_2 n$ 以內。

def find(node):
    if node == dsu[node]:
        return node
    parent = find(dsu[node])
    dsu[node] = parent  # 路徑壓縮
    return parent

def merge(a, b):
    a, b = find(a), find(b)
    if a == b: return  # 原本就同塊 不合併
    if rank[a] == rank[b]:
        rank[a] += 1
    if rank[a] > rank[b]:  # 按秩合併
        dsu[b] = a
    else:
        dsu[a] = b

因此以下其實不是正規的 DSU，雖然有「路徑壓縮」但沒有嚴格「按秩合併」，而是粗略地根據連通塊寶藏價值總和進行合併，為了省空間。

也使以下這個解法達到理論最佳空間複雜度，因為寶藏價值 $\ge 0$，而 index 也是 $\ge 0$，可以用非負整數表示寶藏價值總和（輸入讀進來可以直接用），用負數表示 DSU 父節點，而寶藏價值則存儲在父節點，因為 DSU 只需要能夠判斷一個節點是不是父節點就好，一般來講會存 rank，這題則為了省空間改存寶藏價值。

但 index 明明就是 $\ge 0$，要如何轉到 $\lt 0$？單純取負數會導致 $0$ 被共用，因此可以取負再 $-1$，就等於是取補數。

以下的迭代式 DSU 在我所知的範圍內只有我會這樣寫，因為只要好好地按秩合併就不會被卡遞迴深度，而且應該也很少題會卡 DSU 的合併樹高，但總之我寫 Python 的宗旨就是「寫迭代不寫遞迴」。

$Time: O(n + m \times \alpha(n)), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n, m = map(int, e().split())
    # dsu[int]: 正數: 該連通塊寶藏總和, 負數: 父節點index的補數
    dsu = list(map(int, e().split()))

    for _ in range(m):
        a, b = map(int, e().split())

        # 找根
        ra, pa = ~a, dsu[a]
        rb, pb = ~b, dsu[b]
        while pa < 0:
            ra, pa = pa, dsu[~pa]
        while pb < 0:
            rb, pb = pb, dsu[~pb]

        # 合併
        if ra == rb:  # 本來就同個連通塊
            nr = ra
        elif pa >= pb:  # 取寶藏總和較大的為新的根
            dsu[~ra] += pb
            nr = dsu[~rb] = ra
        else:
            dsu[~rb] += pa
            nr = dsu[~ra] = rb

        # 路徑壓縮
        pa, pb = dsu[a], dsu[b]
        while pa < 0:
            dsu[a] = nr
            a, pa = ~pa, dsu[~pa]
        while pb < 0:
            dsu[b] = nr
            b, pb = ~pb, dsu[~pb]

    print(max(dsu))  # 取最大寶藏總和
main()

### [P-7-3. 機器人走棋盤](https://judge.tcirc.tw/problem/d092)

方格題除了可以加入一圈 sentinel（Python 只需要圍右邊和下面，因為 `list[-1]` 會取到 `list` 的尾部），還能將二維平面壓成一維，就是把每一橫行接在一起，使用各種內建函式（像是第 `12` 行的 `min`）或要取值時都更快更好寫，只是如果沒有圍上一層 sentinel 的話，左右邊界就需要用 `% n` 來判斷，反而容易錯。

以下的實作中事先將 `float("INF")` 存進一個變數 `inf`，確保方格內所有的 `inf` 都是指向同一個物件，如此一來就能用 `is` 判斷，比較快也比較可靠。

$Time: O(m \times n), Space: O(m \times n)$

def main():
    from sys import stdin
    from itertools import chain, repeat
    e = stdin.readline
    inf = float("INF")
    sentinel = (inf, )

    m, n = map(int, e().split())
    n += 1  # 每一行最後都會塞inf作為sentinel 每行變成n+1個格子
    l = list(chain.from_iterable(chain(map(int, e().split()), sentinel)
                                 for _ in range(m)))  # 壓成一維
    m, i = min((v, i) for i, v in enumerate(l))  # 取得最小值作為起點
    l[i] = inf
    l.extend(repeat(inf, n))  # 最後一行加一排inf 防止上下出界

    ans = m
    d = (1, -1, n, -n)  # 往四周移動
    while True:
        # 找四周最小值
        m, i = min((l[i+di], i+di) for di in d)
        if m is inf: break  # 無路可走
        l[i] = inf
        ans += m
    print(ans)
main()

### [P-7-4. 方格棋盤的最少轉彎數路線](https://judge.tcirc.tw/problem/d093)

將「轉彎次數」當作距離作最短路，一樣是 BFS 就好了。

吳邦一教授的範例程式中，是對每個格子找上下左右第一個牆壁並更新最短轉彎次數，時間複雜度為 $O(m \times n \times (n + m))$，但實際上有很多冗餘的遍歷，在一條很長的直線路徑上，每個點都會跑到端點，理論上同方向上同一格只需要遍歷一次即可，但有兩個方向，因此可以用兩個 bit 來記錄各方向是否遍歷過，就能夠避免重複遍歷了。

每輪 BFS 就是同個方向走到底，路上對每個格子新增另一個方向的下一輪 BFS（轉向的概念）。實作上同樣壓成一維陣列再操作。

$Time: O(m \times n), Space: O(m \times n)$

def main():
    from sys import stdin
    from itertools import repeat
    e = stdin.readline

    m, n = map(int, e().split())
    # 特判 1*1方格 (雖然沒有這個測資)
    if m == n == 1: return print(0)
    # 輸入(保留最後的\n 作為sentinel) 轉碼 壓成一維
    # 編碼: 使用二進位記錄每個格子走過了甚麼方向 00未 01橫 10豎 11都走過(或是牆壁)
    l = [(0 if i == "0" else 3) for _ in range(m) for i in e()]
    l.extend(repeat(3, n))
    n += 1  # 每一行最後加了sentinel 行格數+1
    end = m * n - 2  # 計算終點的index

    ans = 0  # 當前轉彎數
    d = (1, -1, n, -n)  # 前進方向: 右左下上
    cur = [(0, 0), (0, 2)]  # 第一格可以往右或往下
    l[0] = 3
    while cur:
        nxt = []
        for i, dd in cur:
            di, dn = d[dd], d[dd ^ 2]  # 當前方向, 轉彎方向
            cm = dd + 2 >> 1  # 當前方向的 bit mask
            nm = 3 ^ cm  # 轉彎後的 bit mask
            l[i] |= cm  # 增加該格已造訪的方向
            while True:
                # 到終點
                if i == end: return print(ans)
                # 嘗試轉彎
                if l[i] & nm == 0:  # 確保同格子同方向不要重複跑
                    if l[i + dn] & nm == 0:
                        nxt.append((i, dd ^ 2))
                    if l[i - dn] & nm == 0:
                        nxt.append((i, dd ^ 3))
               # 前進一步
                i += di
                if l[i] & cm: break  # 碰到造訪過的格子 跳出
                l[i] |= cm  # 增加該格已造訪的方向
        cur = nxt
        ans += 1
    # 整個bfs完都沒到終點
    print(-1)
main()

### [Q-7-5. 闖關路線](https://judge.tcirc.tw/problem/d094)

每次最多傳送一次，佛心過頭了。

以下是我嘗試的另一種 BFS 方式，主要想法一樣但不新開空間，單純兩個列表交替使用，理論上會更快（少掉新的 `list` 在尚短的時候持續新開空間的開銷），但時間差異不大就是了。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n, p, l, r = map(int, e().split())
    if p == 0: return print(0)
    # 將出界的傳送點設為已造訪
    s = [i if 0 <= i < n else None for i in map(int, e().split())]

    ans = 1
    cur, nxt = [0, None], [None]
    s[0] = None
    while cur[0] is not None:
        nxtidx = 0
        for i in cur:
            if i is None: break
            for ni in (i - l, i + r):
                # 左右走出界
                if not (0 <= ni < n): continue
                # 傳送一次
                ti = s[ni]
                # 是否到目的地了
                if ti == p: return print(ans)
                # 已造訪就跳出
                if ti is None: continue
                # 沒造訪就加入queue
                s[ni] = None
                nxt[nxtidx] = ti
                nxtidx += 1
                if nxtidx == len(nxt):
                    nxt.append(None)
        nxt[nxtidx] = None
        cur, nxt = nxt, cur
        ans += 1
    print(-1)
main()

### [P-7-6. DAG 的最長與最短路徑](https://judge.tcirc.tw/problem/d095)

怎麼說呢......就是一般的 DAG 遍歷，沒什麼特別的。

DAG 的精隨就是利用 `indeg` 資訊遍歷，這題跟最短路無關因此可以用 DFS， Stack 比 Queue 快。加上了一點點簡單的剪枝。

需要注意的是，初始化起點時 `27` 行寫成 `q = [s]` 是不正確的，雖然只有從 `s` 開始才會更新距離，但還是必須從所有 `indeg == 0` 的點開始遍歷，如此其子節點的 `indeg` 才會被正確地更新。

$Time: O(n + m), Space: O(n + m)$

def main():
    from sys import stdin
    e = stdin.readline
    imp = (float("INF"), float("-INF"))

    n, m = map(int, e().split())
    s, t = map(int, e().split())

    indeg = [0] * n
    child = [None] * n
    for _ in range(m):
        u, v, w = map(int, e().split())
        if v == s: continue
        indeg[v] += 1
        if child[u] is None:
            child[u] = [(v, w)]
        else:
            child[u].append((v, w))
    # 特判: 不可能有路
    if child[s] is None or indeg[t] == 0:
        print("No path\nNo path")
        return

    dis = [imp] * n
    dis[s] = (0, 0)
    # 就算沒辦法更新dis 也得把前面的節點跑完 後面的indeg才會正確被消掉
    q = [idx for idx, (i, c) in enumerate(zip(indeg, child))
             if i == 0 and c is not None]
    while q:
        i = q.pop()
        dis_i = dis[i]
        if dis_i is not None:
            dis_i_0, dis_i_1 = dis[i]
        for j, w in child[i]:
            if dis_i is not imp:
                dis_j_0, dis_j_1 = dis[j]
                dis[j] = (min(dis_i_0 + w, dis_j_0),
                          max(dis_i_1 + w, dis_j_1))
            indeg[j] -= 1
            if indeg[j] == 0:
                if j == t:  # 終點沒有indeg了 不可能再更新答案 直接結束DAG遍歷
                    q = None
                    break
                if child[j] is not None:
                    q.append(j)
        child[i] = None  # 單純省記憶體

    if dis[t] is imp:
        print("No path\nNo path")
    else:
        print(*dis[t], sep = "\n")
main()

### [P-7-9. 最短路徑](https://judge.tcirc.tw/problem/d096)

模板題，單源無負權最短路。

大名鼎鼎的 Dijkstra 演算法，簡潔美麗而普遍最佳，締造圖論演算法中的一段神話。

其中一個節點是 $0$ 的時候可以直接將邊加入 `q`，再用 `heapify` 將他變成 heap，因為 `heapify` 是線性的比較快。

因為我們不是用 `decrease_key` 的「正規」方法更新 heap 某節點的距離，而是懶惰地將更短的距離放入 heap 中，在 `heappop` 時，舊的距離必定不會更新最短距離，因此不會有錯，但還是可以做個剪枝，只在「當前距離是最短距離」的時候對其他節點鬆弛（鬆弛是數學上「接近最佳解」的意思，不是指路徑變得更長或更短），也就是 `30` 行的那個 `continue`。

$O(n \times m \log_2 m), Space: O(n + m)$

def main():
    from sys import stdin
    from collections import defaultdict
    from heapq import heappop, heappush, heapify
    e = stdin.readline
    inf = float("INF")

    n, m = map(int, e().split())
    G = defaultdict(list)
    q = []  # min-heap 用來找當前與節點0最小的未確定節點
    ans = [inf] * n  # 維護q中所有節點與節點0的最小距離
    ans[0] = 0
    for _ in range(m):
        u, v, w = map(int, e().split())
        if u == 0 or v == 0:  # 與0的邊不用加進圖 直接進q
            if u == 0: u = v
            if w >= ans[u]: continue  # 篩選
            ans[u] = w
            q.append((w, u))
        else:
            G[u].append((v, w))
            G[v].append((u, w))
    heapify(q)

    while q:
        # 取當前未確定中最短的路徑
        d, i = heappop(q)
        # ans[i]必 <= d 而只有等號成立時 此條路徑才是當前最短
        # 如果等號不成立 那就是較早加入q的較長路徑
        if d > ans[i]: continue
        ans[i] = d
        child = G.pop(i)  # pop掉只是省空間 無邏輯意義
        if child is None: continue
        for j, v in child:
            v += d
            # 如果不是更短的路徑就跳過
            if v >= ans[j]: continue
            ans[j] = v
            heappush(q, (v, j))

    m = c = 0
    for i in ans:
        if i is inf:
            c += 1
        elif i > m:
            m = i
    print(m, c, sep = "\n")
main()

### [P-7-10. 挖坑跳](https://judge.tcirc.tw/problem/d097)

以下這個就是正規的 DSU 了，具備「路徑壓縮」和「按秩合併」。為了方便 find，壓成一維比較好取值。rank 則是直接用面積（也就是子樹大小）代替，樹越高則子樹越大，因此這樣的 rank 仍是正確的；面積必定 $> 1$，所以可以直接取負數，不用取補數。

前半部份第一次遍歷全圖的時候也是使用 DSU 而不是 BFS，因為按照順序更新，只要考慮與左邊和上面的格子合併就好了。

這種需要計算面積的題目，要注意合併時不要將自己的面積再加到自己身上，因此第 `35` 行要判斷 `node != root`。

雖然算不上非常相關，但推個我自己出的 [大智慧學苑的朋友圈（Friendship Groups）](https://hackmd.io/@apcs-simulation-/B14TCOt0C)，可以用 BFS/DFS 或 DSU 解，上 [APCSS Judge](https://apcs-simulation.com/problem/apcs1003) 測試 :D。

$Time: O(m \times n \times \alpha(m \times n)), Space: O(m \times n)$

def main():
    from sys import stdin
    e = stdin.readline

    m, n, k = map(int, e().split())
    # 輸入並壓成一維
    # dsu: list[int|None]: None 土堆, 正數 父節點index, 負數 水坑面積(負)
    dsu = [(-1 if v == "1" else None) for _ in range(m) for v in e() if v != " "]
    n += 1  # 每一行最後都加了土堆作為sentinel 所以n要加一
    size = m * n - 1  # 壓成一維後的總長

    ms = cc = 0  # 當前最大面積(負), 當前水坑數量
    d = (0, -1, -n)  # 合併方向 第一次掃只須要往上或左
    for i, v in enumerate(dsu):
        if v is None: continue  # 跳過土堆
        cc += 1  # 遇到水坑

        # 嘗試往上或左合併
        nodes = []
        for node in (i + di for di in d):
            if not 0 <= node < size: continue
            root, pa = node, dsu[node]
            if pa is None: continue
            while pa >= 0:
                root, pa = pa, dsu[pa]
            nodes.append((pa, root, node))
        if len(nodes) == 1: continue  # 只有自己 不用合併

        ns, root, _ = min(nodes)  # 取面積最大(負的最小)者為新root
        for _, _, node in nodes:
            pa = dsu[node]
            while pa >= 0:  # 路徑壓縮
                dsu[node] = root
                node, pa = pa, dsu[pa]
            if node != root:  # 避免合併到自己
                cc -= 1  # 合併 水坑數量減一
                ns += pa  # 貢獻面積
                dsu[node] = root  # 指向新root
        dsu[root] = ns  # 更新新root的面積
        if ns < ms: ms = ns  # 更新最大面積
    ss, sc = ms, cc  # 每一輪最大面積之總和(負), 每一輪水坑數量之總和

    d += (1, n)  # 不只往上,左 還要往右,下合併
    pos = map(int, e().split())
    for i in pos:
        j = next(pos)
        i = (i - 1) * n + (j - 1)  # 轉換成一維index
        if dsu[i] is not None:
            # 原本就是水坑
            ss += ms
            sc += cc
            continue
        # 挖水坑
        dsu[i] = -1
        cc += 1

        # 嘗試往四周合併
        nodes = []
        for node in (i + di for di in d):
            if not 0 <= node < size: continue
            root, pa = node, dsu[node]
            if pa is None: continue
            while pa >= 0:
                root, pa = pa, dsu[pa]
            nodes.append((pa, root, node))
        if len(nodes) == 1:
            ss += ms
            sc += cc
            continue

        ns, root, _ = min(nodes)
        for _, _, node in nodes:
            pa = dsu[node]
            while pa >= 0:
                dsu[node] = root
                node, pa = pa, dsu[pa]
            if node != root:
                cc -= 1
                ns += pa
                dsu[node] = root
        dsu[root] = ns
        if ns < ms: ms = ns
        ss += ms
        sc += cc
    # 面積總和存的是負值 要反過來再輸出
    print(-ss, sc, sep="\n")
main()

### [P-7-12. 最小生成樹](https://judge.tcirc.tw/problem/d098)

DSU 的經典例題。

貪心地從小成本的邊開始連，不能連則跳過。

為何可以貪心？一個不嚴謹但直覺的想法：既然從小邊開始挑，若是 $u, v$ 兩點尚未連接，他們總歸是要連起來的，要是錯過了當前的邊 $(u, v)$，之後連接了那兩點的那條路上，將任意一個權重比 $(u, v)$ 大的換成他，連接的點不變，權重卻會減少。

一樣是完備的 DSU，rank 用負數表示，從 $-1$ 往下表示樹高增加。

不得不提的部分，`32` 和 `34` 行的賦值寫法非常之毒瘤，Python 處理這種連鎖賦值的順序是 1.計算等號最右邊的值 2.將左邊的一連串東西，由左而右將第一步計算的值賦值給他，例如：

a = b = c + d
# 等價於
val = c + d
a = val
b = val

乍看之下沒什麼問題，但 `a`, `b` 的賦值順序在下面有差：

dsu[ra] = ra = rb
# 等價於
dsu[ra] = rb
ra = rb

ra = dsu[ra] = rb
# 等價於
ra = rb
dsu[ra] = rb
# 等價於
ra = rb
dsu[rb] = rb

明顯後者爛掉了，因此應避免使用這種容易有歧義的賦值方法，我這裡寫是為了當反面教材，~~絕對不是因為我某段時期的 coding style 很毒瘤。~~

$Time: O(\text{sort} + n \times \alpha(n)), Space: O(n)$

def main():
    from sys import stdin
    from operator import itemgetter
    e = stdin.readline

    n, m = map(int, e().split())
    if m < n - 1: return print(-1)  # 邊數不夠
    # 邊按照權重升冪排列
    s = sorted((tuple(map(int, e().split())) for _ in range(m)), 
               key=itemgetter(2))

    ans = 0
    dsu = [-1] * n
    for a, b, w in s:
        # 找根
        ra, pa = a, dsu[a]
        rb, pb = b, dsu[b]
        while pa >= 0:
            ra, pa = pa, dsu[pa]
        while pb >= 0:
            rb, pb = pb, dsu[pb]

        # 根不同才合併
        if ra != rb:
            ans += w  # 增加成本
            n -= 1  # 區塊數-1
            if n == 1:
                # 已經只剩一個區塊就結束
                return print(ans)
            if pa == pb: dsu[ra] -= 1
            if pa <= pb:
                dsu[rb] = rb = ra
            else:
                dsu[ra] = ra = rb

        # 路徑壓縮
        pa, pb = dsu[a], dsu[b]
        while pa >= 0:
            dsu[a] = ra
            a, pa = pa, dsu[pa]
        while pb >= 0:
            dsu[b] = rb
            b, pb = pb, dsu[pb]

    print(-1)  # 連不成樹
main()

### [Q-7-7. AOV 最早完工時間](https://judge.tcirc.tw/problem/d099)

這題考的是 AOV 的基本概念，其實就是做一次拓撲排序再反過來遍歷一次，途中記錄各種時間就好了。

<!-- TODO: 剪枝解法 -->

$Time: O(n + m), Space: O(n + m)$

def main():
    from sys import stdin
    e = stdin.readline

    n, m = map(int, e().split())
    w = tuple(map(int, e().split()))

    G = [None] * n
    indeg = [0] * n
    for _ in range(m):
        a, b = map(int, e().split())
        indeg[b-1] += 1
        child = G[a-1]
        if child is None:
            G[a-1] = [b-1]
        else:
            child.append(b-1)

    est = [0] * n  # earliest start time 最早開工時間
    ans = 0  # 最早完工時間 = max(let) 即為所求
    path = [i for i, v in enumerate(indeg) if v == 0]
    for i in path:
        time = est[i] + w[i]
        child = G[i]
        if child is None:  # leaf
            if time > ans:
                ans = time
            continue
        for j in child:
            if time > est[j]:
                est[j] = time
            indeg[j] -= 1
            if indeg[j] == 0:
                path.append(j)
    let = [ans] * n  # latest end time 最晚完工時間
    for i in reversed(path):
        child = G[i]
        if child is not None:
            let[i] = min(let[j] - w[j] for j in child)
    print(ans)
    # 關鍵節點: 最早開工時間 + 工時 = 最晚完工時間
    print(*(i for i, (a, b, c) in enumerate(zip(est, w, let), 1) if a + b == c))
main()

### [Q-7-8. 小寶的著色問題](https://judge.tcirc.tw/problem/d100)

裸二分圖檢測。
這題 Python 在中一中沒辦法拿滿，需要用 PyPy。

有兩種解法：1. 存鄰接表，用 BFS 或 DFS 遍歷、2. 用 DSU 在線加邊同時維護顏色。

解法 1 很直覺，遇到新的子圖就隨便塗色一個節點，遍歷整個圖同時依照相鄰點填色即可，我直接放舊 code：

$Time: O(t \times m), Space: O(t \times (n+m))$

def main():
    from sys import stdin
    from collections import defaultdict
    e = stdin.readline

    def solve():
        n, m = map(int, e().split())
        if m == 0: return "yes"  # 必須直接return 不能把下一行讀給l
        l = map(int, e().split())

        g = defaultdict(list)
        c = [None] * n
        for _ in range(m):
            a, b = next(l), next(l)
            g[a].append(b)
            g[b].append(a)

        cur = []
        while g:
            if not cur:  # 一個連通塊結束 找新一塊
                item = g.popitem()
                cur.append(item)
                c[item[0]] = True  # 第一個節點填色
            nxt = []
            for i, v in cur:
                ci = c[i]
                for j in v:  # 確認鄰居們的顏色
                    cj = c[j]
                    if cj is None:  # 尚未塗色
                        c[j] = not ci  # 填相反色
                        val = g.pop(j, None)
                        if val is not None:
                            nxt.append((j, val))
                    elif cj is ci:  # 確保顏色相反
                        return "no"
            cur = nxt
        return "yes"

    t = int(e())
    print("\n".join(solve() for _ in range(t)))
main()

解法 2 需要仔細維護顏色。

若邊連接的兩個節點在同一個子圖，要能夠快速判斷兩者的顏色是否相同（聽起來還好）；若在相異子圖，則需要合併兩者（DSU 輕易辦到）、使兩節點異色（可能需要翻轉其中一圖的顏色？這怎辦？）

如果直接維護當前節點的「絕對顏色」，則翻轉顏色必然 $O(n)$，因此要維護更「局部」的資訊，善用 DSU 的特性，維護「當前節點與父節點是否異色」，則找根時只要沿路將這個「異色」資訊 $\oplus$ 起來，就知道當前節點相對於根的顏色了，合併時只需要修改其中一個根的顏色。

實作上，可以把「異色」資訊跟 DSU 節點資訊用位元運算壓在一個 `int` 裡面，省空間增效率。

因為是在線算法，實務上比遍歷還快一些。

$Time: O(t \times m \times \alpha(n)), Space: O(t \times n)$

def main():
    from sys import stdin
    e = stdin.readline

    def solve():
        def find(x: int) -> int:  # 遞迴式 DSU (偷懶)
            p = dsu[x]
            if p < 0: return x << 1
            # 路徑壓縮 同時維護顏色
            dsu[x] = r = find(p >> 1) ^ (p & 1)
            return r  # 回傳值包含顏色資訊

        n, m = map(int, e().split())
        if m == 0: return "yes"  # 必須直接return 不能把下一行讀給it

        # dsu[x]  & 1 表示"是否與父節點顏色相異" (根必為0)
        # dsu[x] >> 1 正數為父節點 負數表示根的rank
        dsu = [-2] * n  # 初始化為 rank -1 的根(顏色與自己相同 最低位0)
        it = map(int, e().split())  # 讀入邊
        for a, b in zip(it, it):  # 一次讀取兩個數字
            ra, rb = find(a) >> 1, find(b) >> 1  # 查詢並路壓
            if ra == rb:  # 兩點連通
                if dsu[a] & 1 == dsu[b] & 1:
                    return "no"  # 同色(與根節點關係等價)則非二分圖
            else:  # merge
                # 按秩合併
                if dsu[ra] == dsu[rb]: dsu[ra] -= 2
                elif dsu[ra] > dsu[rb]: ra, rb = rb, ra
                # 合併 並維護合併後 rb 的顏色
                dsu[rb] = (ra << 1) | (dsu[a] & 1) ^ (dsu[b] & 1) ^ 1
        return "yes"

    t = int(e())  # 多筆測資
    print("\n".join(solve() for _ in range(t)))
main()

### [Q-7-11. 紅白彩帶](https://judge.tcirc.tw/problem/d101)

這題分成兩個部分：合併紅色彩帶、維護最長最短。

前者可以用 DSU 輕鬆辦到，但仔細想想，我們真的需要 DSU 嗎？題目保證塗在白色格子上，代表紅色彩帶**只有端點有意義**，因此可以用「左右端點互相紀錄」的方式，概念上類似 doubly linked list，而這題能只存單邊 link，合併只需要維護新的端點即可。

至於後者，因為彩帶只會變長，最長很好求，而最短就比較難了，可以用 heap 惰性地維護，每次找最小值時，再依照端點資訊判斷他是否 out of date。

$Time: O(n \log_2 n), Space: O(n)$

def main():
    from sys import stdin
    from heapq import heappop, heappush
    e = stdin.readline

    e()  # n, k 用不到
    l = [0, *map(int, e().split()), 0]

    M, m = 0, []
    it = enumerate(l)
    for i, v in it:
        if v == 0: continue
        # 找到左端點
        le = i
        # 找端點
        while v == 1:
            i, v = next(it)
        r, ri = i - le, i - 1
        # 左右端點互相紀錄
        l[le], l[ri] = ri, le
        # 更新長度
        if r > M: M = r
        heappush(m, (r, le))

    sM, sm = M, m[0][0]  # 所求
    for i in map(int, e().split()):
        l[i] = i
        # 找左右端點
        le = l[i - 1]
        if le == 0: le = i
        ri = l[i + 1]
        if ri == 0: ri = i
        # 左右端點互相紀錄
        l[le], l[ri] = ri, le
        # 更新長度
        r = ri - le + 1
        if r > M: M = r
        heappush(m, (r, le))
        mv, mp = m[0]
        # 將不合(太舊)的長度剃除
        # 也可以寫 l[mp] - l[l[mp]] + 1 != mv
        while mp != l[l[mp]] or l[mp] - mp + 1 != mv:
            heappop(m)
            mv, mp = m[0]
        sM += M
        sm += mv
    print(sM, sm, sep="\n")
main()

### [P-8-1 樹上的推銷員](https://judge.tcirc.tw/problem/d102)

最小字典序的樹上遍歷。

分為兩部分：總距離、最小字典序。前者很明顯是每條邊都經過兩次（對於一條連接父子兩節點的邊而言，最短路為遍歷父-子-子的所有子樹-子-父，所以經過兩次）；後者則因為要求字典序而有局部最佳性，可以貪心。

將輸入存成雙向鄰接圖以後，對每一個節點的鄰接節點按照編號排序，再遵循「所有子樹走完再走回父節點」的規則，就只剩實作問題了。

對於某個節點而言，「依序遍歷」每個子樹的部分可以用遞迴 DFS、每個節點存一個 `index` 表示遍歷到第幾個鄰接節點，或者 pythonic 一點，將鄰接串列轉成 iterator，讓 Python 底層自動幫你維護 index，這也是以下解法使用的方案。

$Time: O(\text{sort} + n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    G = [[] for i in range(n)]
    dis = 0
    for i in range(n - 1):
        a, b, w = map(int, e().split())
        G[a].append(b)
        G[b].append(a)
        dis += w
    for i, v in enumerate(G):
        v.sort()  # 按照字典序排列 O(nlogn)
        G[i] = iter(v)  # 做成iterator方便後面遍歷
    print(dis << 1)  # 每條路都會剛好經過兩次

    pa = [None] * n
    pa[0] = -1  # sentinel (is not None)
    ans = [0]  # 從零開始 字典序最小
    for i in ans:
        for j in G[i]:  # 由小到大找還沒去過的節點
            if pa[j] is None:  # 找到還沒去過的節點
                pa[j] = i  # 才知道回溯的時候要找誰
                ans.append(j)
                break
        else:
            if i: ans.append(pa[i])  # 這棵子樹遍歷完了 回溯
            # 否則代表已經回到0 遍歷結束
    print(*ans)
main()

然而上面排序的時間複雜度是 $O(n \log_2 n)$，實際上可以用 counting sort 的概念做到 $O(n)$：

$Time: O(n), Space: O(n)$

# counting sort O(n)
G_ = [[] for _ in range(n)]
for i, v in enumerate(G):
    for j in v: G_[j].append(i)  # 按照字典序排列
G = tuple(map(iter, G_))  # 做成iterator方便後面遍歷
del G_

實際上反而慢了一些，因為基於 C 的 powersort 真的巨快。
但如果是用 C 或 C++ 加上「鏈式前向星」來寫的話，效能提升會很有感：

#include <bits/stdc++.h>
#define IO cin.tie(0)->sync_with_stdio(0);
#define M(x, v) memset(x, (v), sizeof(x))
#define REP(i, s, t) for (int i = (s); i < (t); ++i)
using namespace std;
void solve();

int main() {
    IO;
    solve();
    return 0;
}

const int N = 5e4;

int head[N], deg[N], idx[N], to[N << 1], nxt[N << 1];
int adj[N << 1];  // sorted adj-list

void solve() {
    // M(deg, 0);
    M(head, -1);
    int n; cin >> n;
    int dis = 0, ei = 0;
    REP(i, 0, n - 1) {
        int a, b, w; cin >> a >> b >> w;
        dis += w;
        to[ei] = b, nxt[ei] = head[a], head[a] = ei++;
        to[ei] = a, nxt[ei] = head[b], head[b] = ei++;
        ++deg[a], ++deg[b];
    }
    cout << (dis << 1) << '\n';

    // counting sort
    REP(i, 1, n) deg[i] += deg[i-1];
    memcpy(idx, deg, sizeof(idx));
    for (int i = n; i--; ) {
        for (int ei = head[i]; ei != -1; ei = nxt[ei]) {
            int j = to[ei];
            adj[--idx[j]] = i;
        }
    }

    M(head, -1);  // -> int parent[N]
    head[0] = -2;  // end sentinel
    for (int i = 0, j; i != -2; ) {
        cout << i << ' ';
        for (; idx[i] < deg[i]; ++idx[i]) {
            j = adj[idx[i]];
            if (head[j] == -1) {
                head[j] = i, i = j;
                break;
            }
        }
        if (i != j) i = head[i];
    }
}

### [P-8-2. 物流派送系統](https://judge.tcirc.tw/problem/d103)

這題很貼心，邊的方向都給好了，不用建雙向邊，直接當 DAG Bottom-up 帶權遍歷即可。

這題就能見到我這種 BFS 方法的優勢：能直接計算遍歷層數。

另一種方法是每個父節點紀錄自己的子節點，從根 Top-down 直接做一次遍歷（相當於拓撲排序），再將順序反轉後就可以 Bottom-up 了，可以不用維護 `indeg`，但就得另外計算層數。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    pa = [None] * n
    indeg = [0] * n
    for i in range(1, n):
        x, w = map(int, e().split())
        pa[i] = (x, w)
        indeg[x] += 1

    t, c = [0] * n, 0  # 所求
    cur = [i for i, v in enumerate(indeg) if v == 0]
    while cur:
        nxt = []
        for i in cur:
            p, w = pa[i]
            tp, w = t[p], w + t[i]
            if w > tp: t[p] = w  # 更新運輸時間
            indeg[p] -= 1
            if p != 0 and indeg[p] == 0:
                nxt.append(p)
        cur = nxt
        c += 1  # 執行輪數即為最大層數
    print(t[0], c, sep="\n")
main()

### [P-8-3. 購物中心選位置](https://judge.tcirc.tw/problem/d104)

找樹重心的裸題。重心有 $1 \sim 2$ 個，$2$ 個的話必相鄰，這題要找離根較遠，也就是高度較低的重心。

就是 Bottom-up 算子樹大小，距離總和則用貢獻法算。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    pa = [tuple(map(int, e().split())) for i in range(n - 1)]
    indeg = [0] * n
    for p, _ in pa:
        indeg[p] += 1

    half = n + 1 >> 1
    ans, dis = None, 0
    siz = [0] * n  # 子節點個數
    cur = [i for i, v in enumerate(indeg) if v == 0]
    while cur:
        nxt = []
        for i in cur:
            p, w = pa[i - 1]
            s = siz[i] + 1  # 自己的子樹大小(加上自己)
            # 取第一個遇到(離根較遠)的中位點
            if ans is None and s >= half:
                ans = i
            # 更新距離
            dis += w * min(s, n - s)
            # 更新父節點資訊
            siz[p] += s
            indeg[p] -= 1
            if p != 0 and indeg[p] == 0:
                nxt.append(p)
        cur = nxt
    print(ans, dis, sep="\n")
main()

樹重心的性質很好，因為只有常數個（$1 \sim 2$），所以可以將無根樹以重心為根轉換成常數個有根樹，使用 tree hashing 做樹同構判斷的時候這個性質很有幫助；因為會將大小 $n$ 的樹拆分成節點樹至多 $n/2$ 的子樹，因此可以用於樹分治，分治層數最多 $O(\log_2 n)$ 層、每一層找重心 $O(n)$、總時間複雜度 $O(n \log_2 n)$，樹分治（又稱重心剖分）適合解決樹上路徑問題。

### [P-8-5. 自動分裝](https://judge.tcirc.tw/problem/d105)

模擬題，分成兩部分：計算子樹總重、放貨物並更新路徑上的重量。前者可以 Bottom-up 當 DAG 做，後者就是直接 Top-down 模擬（我也不知道有甚麼好說的ww）。
很多毒瘤人會用 DFS 遞迴處理後者，但他明明就是單純的遍歷而已，請好好思考。

後者就只能暴力 $O(樹高)$ 模擬，應該沒有甚麼神奇黑魔法可以快速解決。

$Time: O(mn), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n, m = map(int, e().split())
    w = [0] * n
    w.extend(map(int, e().split()))
    q = map(int, e().split())

    # 1-based
    indeg = [0] * n
    indeg[0] = None  # 節點0為對齊用 用不到
    child = [None] * n
    pa = [1] * n
    for _ in range(n - 1):
        p, s, t = map(int, e().split())
        child[p] = (s, t)
        if s < n:
            pa[s] = p
            indeg[p] += 1
        if t < n:
            pa[t] = p
            indeg[p] += 1

    # Bottom-up 更新子樹總重
    cur = [i for i, v in enumerate(indeg) if v == 0]
    while cur:
        nxt = []
        for i in cur:
            s, t = child[i]
            w[i] += w[s] + w[t]
            # 嘗試遍歷父節點
            p = pa[i]
            indeg[p] -= 1
            if indeg[p] == 0:
                # 到根1時其父也標示為1 indeg會變-1而不會再遍歷一次
                nxt.append(p)
        cur = nxt
    del pa

    ans = []
    for k in q:
        i = 1
        while i < n:
            s, t = child[i]
            # 選較輕 左優先
            i = s if w[s] <= w[t] else t
            w[i] += k  # 更新重量
        ans.append(i)
    print(*ans)
main()

### [P-8-7. 寶石的顏色](https://judge.tcirc.tw/problem/d106)

雖然只能選一種顏色，但我們可以每一種顏色都維護，最後再挑數量最多的顏色（先射一堆箭再畫靶:D）。

因為 Python 的遞迴容易炸，所以手刻一個 Stack 並使用 iterator 來模擬遞迴的行為。

而顏色離散化的部分，一種寫法是用 `dict`、沒見過的判一下新增進去；一種是用 `defaultdict`；一種是用以下寫法，把所有顏色都事先開好，這樣速度也比較快。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    from itertools import filterfalse
    e = stdin.readline

    n = int(e())
    l = tuple(map(int, e().split()))

    G = [[] for i in range(n)]
    for _ in range(n - 1):
        a, b = map(int, e().split())
        G[a].append(b)
        G[b].append(a)
    for i, v in enumerate(G):
        # 做成iterator方便遍歷
        G[i] = iter(v)

    ans = cur = 0
    stk = []  # DFS路徑
    # 紀錄當前各顏色個數
    cnt = dict.fromkeys(l, 0)
    c = l[0]
    cnt[c] = 1
    # 紀錄是否到訪過
    vis = [False] * n
    vis[0] = True
    key = vis.__getitem__
    while True:
        # 找到下一個尚未造訪的子樹 vis[nxt] == False
        nxt = next(filterfalse(key, G[cur]), None)
        if nxt is None:  # 子樹都遍歷過 回溯
            if not stk: break
            cnt[c] -= 1
            cur = stk.pop()
            c = l[cur]
        else:  # 遇到一個新的節點 更新顏色和答案
            vis[nxt] = True
            stk.append(cur)
            cur, c = nxt, l[nxt]
            val = cnt[c] = cnt[c] + 1
            if val > ans: ans = val
    print(ans)
main()

### [P-8-8. 樹的最大獨立集](https://judge.tcirc.tw/problem/d107)

樹的最大獨立集可以樹上貪心線性解決，也就是此題；若是帶權則可以樹上 DP，變成 [P-8-11-公司派對](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part2#P-8-11-%E5%85%AC%E5%8F%B8%E6%B4%BE%E5%B0%8D)。

而在普通的無向圖上找最大獨立集是 NP-hard 的，也沒有快速的近似方法，可以 1. 枚舉所有可能 $O(2^n)$ 並 $O(n)$ 驗證（假設位元操作 $O(1)$）、2. 位元 DP $O(2 ^ n)$ 狀態 $O(n)$ 轉移、3. 實務上最快會是遞迴枚舉剪枝 $O(?)$ 解決。

簡單來講就是貪心地取子節點，若此點可選則把父節點標記不能選。

實作上用 Bottom-up 遍歷，把「此點是否可選」維護在 `indeg[i] & 1`，也就是其最低的 1 bit，這樣就可以用位元運算快速標記，~~除了比較帥以外沒有任何實質意義~~。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    pa = tuple(map(int, e().split()))

    indeg = [1] * n  # 最低 1 bit 用來存是否被選
    for p in pa: indeg[p] += 2

    ans = 0
    # 找葉子 indeg == 0
    cur = [i for i, v in enumerate(indeg) if v == 1]
    while cur:
        nxt = []
        for i in cur:
            p = pa[i - 1]
            ans += indeg[i]  # indeg == 0 只剩最低 1 bit
            indeg[p] &= ~indeg[i]  # 選了自己 父就不能選
            indeg[p] -= 2
            if p != 0 and indeg[p] <= 1:
                nxt.append(p)
        cur = nxt
    print(ans + indeg[0])  # 補統計根節點是否被選
main()

### [Q-8-6. 樹狀圖的距離總和](https://judge.tcirc.tw/problem/d108)

貢獻法的經典題，只要想到答案為「每一邊權 $\times$ 在多少組點對之間」就迎刃而解。

而後者的總數顯然為 $O(n ^ 2)$，需要想個辦法 $O(n)$ 內計算：對於每一條邊而言，他的兩端總共有各 $a, b$ 個節點，則他被包含在 $a \times b$ 組點對之間，「兩端各有多少節點」就是兩端**較低**的節點，在有根樹上的「子樹大小」和「$n-$ 子樹大小」，這能在 $O(n)$ 內輕易算出來。

這題直接給明了父、子節點的上下關係，但輸入是毒瘤的 1-based，然而他是單行輸入，為了免去多寫一個迴圈把裡面數字都改回 0-based 的效率損耗，這題就多開一格，暫且委屈一下共體「時」艱。
如果沒有給明上下關係，則要再判斷一下，拿較低節點的子樹大小來計算。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    # 1-based, start = 2
    pa = tuple(zip(map(int, e().split()), map(int, e().split())))

    indeg = [0] * (n + 1)
    indeg[0] = None  # 用於對齊 用不到
    for p, _ in pa: indeg[p] += 1

    ans = 0
    h = [1] * (n + 1)
    cur = [i for i, v in enumerate(indeg) if v == 0]
    while cur:
        nxt = []
        for i in cur:
            p, w = pa[i - 2]
            x = h[i]
            # 更新距離總和
            ans += w * x * (n - x)
            # 更新父節點子樹大小
            h[p] += x
            indeg[p] -= 1
            if p != 1 and indeg[p] == 0:
                nxt.append(p)
        cur = nxt
    print(ans << 1)  # 同一邊要被算兩次
main()

### [P-8-11. 公司派對](https://judge.tcirc.tw/problem/d109)

定義 $dp_i$ 為 $i$ 整顆子樹的最大權獨立集，$dp_{i,0}$ 為不選 $i$ 的情況、$dp_{i,1}$ 為選 $i$ 的情況。
則：
$$
dp_{i,0} = \sum_{j \in i} \max(dp_{j,0}, dp_{j,1}), \quad dp_{i,1} = \sum_{j \in i} dp_{j,0}
$$
父節點不選時，子節點可選可不選；父節點選時，子節點必不能選。

實作上一樣 Bottom-up 進行 DP 更新。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n, r = map(int, e().split())
    pa = [None] * n
    dp = [(0, r)] * n
    indeg = [0] * n
    for i in range(1, n):
        p, r = map(int, e().split())
        pa[i] = p - 1
        dp[i] = (0, r)
        indeg[pa[i]] += 1

    cur = [i for i, v in enumerate(indeg) if v == 0]
    while cur:
        nxt = []
        for i in cur:
            p = pa[i]
            i0, i1 = dp[i]
            p0, p1 = dp[p]
            # 轉移
            dp[p] = (
                # 父節點不選 自己可選可不選
                p0 + (i0 if i0 > i1 else i1),
                # 父節點選 自己不能選
                p1 + i0
            )
            indeg[p] -= 1
            if p != 0 and indeg[p] == 0:
                nxt.append(p)
        cur = nxt
    i0, i1 = dp[0]  # 根節點的 dp 代表整棵樹
    print(i0 if i0 > i1 else i1)
main()

### [P-8-13. 不同成本的購物中心](https://judge.tcirc.tw/problem/d110)

這題很有料，最小權支配集。

定義 $dp_i$ 為 $i$ 整顆子樹的最小權支配集，$dp_{i,0}$ 為不選 $i$ 且 $i$ 尚未被支配的情況、$dp_{i,1}$ 為不選 $i$ 但 $i$ 已被子節點支配（任一子節點有選）的情況、$dp_{i,2}$ 為選 $i$ 的情況（$i$ 理所當然被自己支配）。
則：

$$
dp_{i,0} = \sum_{j \in i} \min(dp_{j,1}, dp_{j,2})
$$

$$
dp_{i,1} = \big( \sum_{j \in i} \min(dp_{j,1}, dp_{j,2}) \big) + \min_{j \in i} \big( {dp_{j,2} - \min(dp_{j,1}, dp_{j,2})} \big)
$$

$$
dp_{i,2} = \sum_{j \in i} \min(dp_{j,0}, dp_{j,1}, dp_{j,2})
$$

然而 $dp_{i,1}$ 的轉移有點複雜，看似要分別維護 $\sum$ 和 $\min$ 的兩個部分，但觀察到其 $\sum$ 的部分即為 $dp_{i,0}$，因此實作上 $dp_{i,1}$ 可以只維護其 $\min$ 的部分，要轉移或計算答案時再加上 $dp_{i,0}$ 即可。

實作上，這題給的是一些無向邊，因此可以先隨便令一點作為根，以他做為起點 Top-down 拓撲排序後再反序遍歷就會變成 Bottom-up。

總之，這題的難點在於要先想出**充足完善**的 DP 狀態（這點最難）、還要想出轉移該如何實作比較方便（$dp_{i,1}$ 的部分）。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    from itertools import islice
    e = stdin.readline
    inf = float("INF")

    n = int(e())
    dp = [(0, inf, x) for x in map(int, e().split())]
    child = [[] for i in range(n)]
    for i in range(n - 1):
        u, v = map(int, e().split())
        u, v = u - 1, v - 1
        child[u].append(v)
        child[v].append(u)

    pa = [False] * n
    pa[0] = True
    top_down = [0]
    for i in top_down:
        for j in child[i]:
            if pa[j] is False:
                pa[j] = i
                top_down.append(j)
    del child

    # bottom-up
    for i in islice(reversed(top_down), n - 1):
        p = pa[i]
        d0, d1, d2 = dp[i]
        d1 += d0
        m = d1 if d1 < d2 else d2
        p0, p1, p2 = dp[p]
        dp[p] = (p0 + m,  # 此點不選 子節點皆需已被支配
                 min(p1, d2 - m),  # 子節點皆需已被支配 且有子節點支配此點
                 p2 + min(d0, d1, d2))  # 選此點 子節點隨意
    d0, d1, d2 = dp[0]
    d1 += d0
    print(d1 if d1 < d2 else d2)
main()

### [P-8-14. 血緣關係](https://judge.tcirc.tw/problem/d111)

求無向圖上兩點之間的最遠距離，即樹直徑。

第一種方法，依照題意好好 DP，對於每個節點維護最長、次長子樹深度。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    pa = [-1] * n
    indeg = [0] * n
    for i in range(n-1):
        a, b = map(int, e().split())
        indeg[a] += 1
        pa[b] = a

    ans = 0
    h1, h2 = [0] * n, [0] * n
    cur = [i for i, v in enumerate(indeg) if v == 0]

    while cur:
        nxt = []
        for i in cur:
            # 更新答案
            c1, c2 = h1[i], h2[i]
            c2 += c1
            if c2 > ans: ans = c2
            # 更新父節點
            p = pa[i]
            if p == -1: # 根節點
                root = i
                continue
            c1 += 1
            if c1 > h1[p]: # 是否能取代第一高的子樹
                h1[p], h2[p] = c1, h1[p]
            elif c1 > h2[p]: # 是否能取代第二高的子樹
                h2[p] = c1
            indeg[p] -= 1
            if indeg[p] == 0:
                nxt.append(p)
        cur = nxt
    print(max(ans, h1[root], h2[root]))
main()

第二種方法，兩次 BFS，先從任意點出發走到最遠點，再由此點出發找到最遠點即為直徑。

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    G = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, e().split())
        G[a].append(b)
        G[b].append(a)

    flag = [False] * n
    cur = [0]  # 任意點出發 找最遠點
    while cur:
        nxt = []
        for i in cur:
            for j in G[i]:
                if flag[j]: continue
                flag[j] = True
                nxt.append(j)
        cur = nxt

    ans = -1  # 算直徑
    cur = [i]  # 從上次的最遠點出發 再走到最遠
    while cur:
        nxt = []
        for i in cur:
            for j in G[i]:
                if not flag[j]: continue
                flag[j] = False
                nxt.append(j)
        cur = nxt
        ans += 1
    print(ans)
main()

### [Q-8-9. 服務中心選位置](https://judge.tcirc.tw/problem/d112)

樹上最小支配集，和最大獨立集本質上是同個問題（圖上最小支配集就是補圖上最大獨立集）。

定義三個狀態：

- `00`：不選此點，未被支配　　　 -> 父節點必選，支配此點 -> 父節點 `| 11`
- `01`：不選此點，已被子節點支配 -> 對父節點無影響　　　 -> 父節點 `| 00`
- `11`：選取此點，已被自己支配　 -> 父節點已被此點支配　 -> 父節點 `| 01`

可以注意到左邊一位代表「是否選取」，右邊一位代表「是否已支配」，如此一來轉移都只需要 `|` 一個數字即可，這就是二進位的魅力！
以下 `((~x & 1) << 1) | (~((x >> 1) ^ x) & 1)` 的公式，就是輸入左側子節點狀態、輸出右側父節點要 `|` 的值。

但根節點還需要特別注意，因為根節點沒有父節點，因此若是根節點為狀態 `00` 則也需要選取他。實作上可以特判（最穩妥）；另一種方法是再增加一個虛點作為根節點的父節點，這樣就能確保父節點必然被支配，而以下實作直接將根節點的父節點設為其本身，讓他「如果未被支配則自己支配自己」，只是在計算支配集點數時，得注意不要重複算到根節點，因此我是待狀態全部更新完再用一個 `sum` 統一計算。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, e().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        G[b].append(a)

    top_down = [0]
    pa = [None] * n
    pa[0] = 0
    for i in top_down:
        for j in G[i]:
            if pa[j] is not None: continue
            pa[j] = i
            top_down.append(j)
    del G

    dp = [0] * n
    t = (3, 0, None, 1).__getitem__
    # t(x) = ((~x & 1) << 1) | (~((x >> 1) ^ x) & 1)
    for i in reversed(top_down):
        dp[pa[i]] |= t(dp[i])
    print(sum(v >> 1 for v in dp))
main()

### [Q-8-10. 竊聽間諜網](https://judge.tcirc.tw/problem/d113)

這題也是樹上最小支配，但前一題是「點支配點」，這題是「點支配邊」，這題比較簡單一點（狀態較少）。

邊上的東西視情況通常會拿到點上做，會比較好實作，像是這題的邊就可以由子節點來紀錄，因為子節點和父節點之間僅有唯一邊。
但這題可以再單純一點：規則簡單來講就是「父子至少一個有選」，因此 Bottom-up 轉移就是「子節點不選則父節點必選」。

這題的輸入極度佛心，保證父節點編號 $\lt$ 子節點，因此不必拓撲排序，直接從編號大的往編號小的做就會是正確的順序。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    dp = [0] * n
    # 倒序 Bottom-up
    for x, pa in zip(reversed(dp), reversed(tuple(map(int, e().split())))):
        dp[pa] |= x ^ 1  # 自己沒選則父節點必選
    print(sum(dp))
main()

### [Q-8-12. 佔領連續的城鎮](https://judge.tcirc.tw/problem/d114)

可以理解為樹上最大區間和，就是做一次拓譜排序後在樹上做卡丹。
注意這題求的是「最大權連通塊」，而不是「最大權路徑」，都可以用卡丹做但細節不一樣，前者單純一點點。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    n = int(e())
    dp = list(map(int, e().split()))
    G = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, e().split())
        a, b = a - 1, b - 1
        G[a].append(b)
        G[b].append(a)

    pa = [None] * n
    pa[0] = -1  # 父節點指向啥都可以
    top_down = [0]
    for i in top_down:
        for j in G[i]:
            if pa[j] is not None: continue
            pa[j] = i
            top_down.append(j)

    ans = 0
    # 卡丹
    for i in reversed(top_down):
        v = dp[i]
        if v < 0: continue
        elif v > ans: ans = v
        dp[pa[i]] += v
    print(ans)
main()

### [Q-8-15. 樹上一位不回家的推銷員](https://judge.tcirc.tw/problem/d115)

觀察到：遍歷所有點的路徑長為「$2 \times$ 道路長度總和 $-$ 起點到終點最短路徑」，最大化後者則答案最小，因此此題其實要算「帶權樹直徑」，因為題目路徑長皆為正整數，因此還是可以用兩次 BFS 算，但因為帶權所以 BFS 沒有特別優勢，以下示範用 Stack 實作 DFS。

$Time: O(n), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline

    def farthest(start: int): # -> tuple[int, int] 從一個節點出發 找離他最遠的節點及距離
        flagged = vis[start] = not vis[start]
        m = (0, start) # 最遠的節點 (距離, 節點)
        append(m)
        while stk:
            d, i = cur = pop()
            # 更新最遠節點
            if cur > m: m = cur
            for j, w in G[i]:
                if vis[j] is flagged: continue
                vis[j] = flagged
                append((d + w, j))
        return m

    n = int(e())
    G = [[] for _ in range(n)]
    s = 0
    for _ in range(n - 1):
        a, b, w = map(int, e().split())
        G[a].append((b, w))
        G[b].append((a, w))
        s += w

    # 初始化dfs資訊
    vis = [False] * n
    stk = []
    pop, append = stk.pop, stk.append

    # 隨便選一個節點 dfs到離他最遠的
    _, i = farthest(0)

    # 以剛剛最遠的節點為起點 dfs到離他最遠的 算出直徑
    d, i = farthest(i)

    # ans = 路徑總和 * 2 - 直徑
    print((s << 1) - d)
main()

### [Q-8-16. 病毒演化](https://judge.tcirc.tw/problem/d116)

樹上 DP 題，易觀察到字串的每個 index 之間不會干擾，因此可以一個一個字元處理。

先示範一個用 `if else` 好好分 case 的，這樣可以把空間開少一點，只有 `@` 需要開四個狀態並好好處理轉移，其他直接傳遞數字即可。但實作麻煩容易錯，實務不建議。

$Time: O(n \times m), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline
    get = "AUGC@".index

    n, m = map(int, e().split())
    s = [None] * n
    pa = [0] * n
    indeg = [0] * n
    for _ in range(n):
        i, j, tmp = e().split()
        i, j = int(i) - 1, int(j) - 1
        s[i] = map(get, tmp)  # 不一次將RNA全部轉換 存個iterator
        pa[i] = j
        if i == j:
            root = i
        else:
            indeg[j] += 1

    path = [i for i, v in enumerate(indeg) if v == 0]
    for i in path:
        p = pa[i]
        indeg[p] -= 1
        if p != root and indeg[p] == 0:
            path.append(p)
    del indeg

    ans = 0
    dp = [None] * n
    sc = [None] * n
    for k in range(m):
        # 初始化每一輪的RNA編碼 DP表
        for i, it in enumerate(s):
            sc[i] = v = next(it)
            dp[i] = [0] * 4 if v == 4 else 0
        # bottom-up DP
        for i in path:
            p, dpi = pa[i], dp[i]
            si, sp = sc[i], sc[p]
            if si == 4:
                # @-@
                if sp == 4:
                    dpp = dp[p]
                    tmp = min(dpi) + 1
                    for x, v in enumerate(dpi):
                        dpp[x] += tmp if tmp < v else v
                # X-@
                else:
                    dp[p] += min(v + (1 if sp != x else 0)
                                 for x, v in enumerate(dpi))
            else:
                # @-X
                if sp == 4:
                    dpp = dp[p]
                    for x in range(4):
                        dpp[x] += dpi + 1
                    dpp[si] -= 1
                # X-X
                else:
                    dp[p] += dpi + (1 if sp != si else 0)
        ans += min(dp[root]) if sc[root] == 4 else dp[root]
    print(ans)
main()

另一種方式是全部都當 `@-@` 在轉移，而 `X` 的狀態將 `X` 以外的格子都設成 $\infty$，實作難度驟降。

$Time: O(n \times m), Space: O(n)$

def main():
    from sys import stdin
    e = stdin.readline
    inf = float("INF")
    get = "AUGC@".index

    n, m = map(int, e().split())
    s = [None] * n
    pa = [0] * n
    indeg = [0] * n
    for _ in range(n):
        i, j, tmp = e().split()
        i, j = int(i) - 1, int(j) - 1
        s[i] = map(get, tmp)  # 不一次將RNA全部轉換 存個iterator
        pa[i] = j
        if i == j:
            root = i
        else:
            indeg[j] += 1

    path = [i for i, v in enumerate(indeg) if v == 0]
    for i in path:
        p = pa[i]
        indeg[p] -= 1
        if p != root and indeg[p] == 0:
            path.append(p)
    del indeg

    ans = 0
    dp = [None] * n
    for k in range(m):
        # 初始化每一輪的RNA編碼 DP表
        for i, it in enumerate(s):
            v = next(it)
            if v == 4:
                dp[i] = [0] * 4
            else:
                dp[i] = [inf] * 4  # X 以外設為 inf
                dp[i][v] = 0  # X 設為 0
        # bottom-up DP
        for i in path:
            p = pa[i]
            mn = min(dp[i]) + 1  # 從其他狀態突變過來
            for x, v in enumerate(dp[i]):
                dp[p][x] += mn if mn < v else v
        ans += min(dp[root])
    print(ans)
main()

## 附件

- [AP325 初見](https://colab.research.google.com/drive/1LyBHbqB0n2lFb1Lt_7EM0gbBOfDTC2H1?hl=en) - 這篇是第一次刷 AP325 時寫的，時間跨距稍微有點大，可以看到很噁心的寫法和最佳解交雜，比較亂，屬於單純的歷程記錄。
- [AP325 二見](https://colab.research.google.com/drive/1lcYD5MQF2cVF3rQ725gSnsKtFc-NcRS-?hl=en) - 這篇即是本文所有程式碼的來源。
- [AP325 精熟到登峰 上篇](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part1) - 上篇連結
- [AP325 精熟到登峰 下篇](https://hackmd.io/@ericshen19555/AP325_Mastering_to_Peak_Part2) - 本文連結

## 參考資料

- [AP325](https://drive.google.com/drive/u/0/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m) by 吳邦一教授
- [AP325-Python](https://hackmd.io/@bangyewu/Hy2kbYLI6/%2Fg2kqHh5_Q4eQnz-mfNu3Kw) by 吳邦一教授