Codeforces 🎨 CF2183F. Jumping Man

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2183F Jumping Man

rating: 2445

Problem Statement

題目簡述

給定一棵 $n$ 個節點的樹（以節點 $1$ 為根），每個節點上有一個小寫英文字母。對於每一個節點 $i$，考慮其子樹中所有可能的「路徑字串」。

路徑定義

一條路徑的定義為：從子樹內任一點出發，每次移動到當前節點的真子樹（Proper Subtree）中的任意節點，重複任意次。將路徑上經過的節點字元拼接形成字串。

題目要求對於每個 $i=1 \dots n$，計算所有生成的不同字串出現次數的平方和，並對 $998244353$ 取模。

Constraints

約束條件

• $1 \le n \le 5000$
• $\sum n \le 5000$

---

思路：DFS 序 + 二維後綴和優化 DP

對於節點 $i$，令 $\text{cnt}_i(t)$ 表示字串 $t$ 在其子樹所有路徑中的出現次數，題目所求即為 $\displaystyle \sum_{t} (\text{cnt}_i(t))^2$。

1. 核心轉化：平方和的組合意義

直接統計平方和困難重重，因此運用平方的組合意義進行轉化：

$$\sum_{t} (\text{cnt}_i(t))^2 \iff \text{從子樹 } i \text{ 的所有路徑中，選出兩條路徑使其生成的字串完全相同的有序配對數}$$

為何等價？

對於某字串 $t$，若它出現了 $\text{cnt}_i(t)$ 次，則選出兩條皆生成 $t$ 的有序路徑對的方案數恰為 $(\text{cnt}_i(t))^2$。
對所有 $t$ 求和，即得原式。

直觀例子

設有 3 顆標籤 “A” 的球、2 顆標籤 “B” 的球：

• 平方和：$3^2 + 2^2 = 13$
• 相同標籤配對數：選兩個 “A” 有 $3 \times 3 = 9$ 種，選兩個 “B” 有 $2 \times 2 = 4$ 種，合計 $13$ 種。

對應本題：

• 「物品」= 子樹內的一條路徑
• 「標籤」= 該路徑生成的字串。

此轉化將「統計所有字串的頻率」簡化為「判斷兩條路徑是否相同」。

而判斷路徑 $P_1$（起於 $u$）與 $P_2$（起於 $v$）是否相同，可以先驗證 $S[u] = S[v]$，再遞迴比較後續路徑，這可以用 DP 來實現。

2. 動態規劃設計

狀態定義：$f(i, j)$ 表示分別以節點 $i$ 和 $j$ 為起點，能生成的「相同路徑對」數量。

路徑可在任意處停止，亦可跳至當前節點的任意 真子孫(Proper Descendants) 繼續延伸。

轉移方程

$$f(i, j) = \begin{cases} 0 & \text{if } S[i] \neq S[j] \\[6pt] \displaystyle 1 + \sum_{u \in \text{subtree}(i)\setminus\{i\}} \sum_{v \in \text{subtree}(j)\setminus\{j\}} f(u, v) & \text{if } S[i] = S[j] \end{cases}$$

• 若 $S[i] \neq S[j]$：首字符不同，無法匹配，貢獻為 $0$。
• 若 $S[i] = S[j]$：首字符匹配，貢獻 $1$（兩路徑均於此結束）；再累加所有後續配對的可能。

答案計算

對於查詢節點 $\text{root}$，其答案為子樹內所有節點對的 $f$ 值總和：

$$\text{Ans}(\text{root}) = \sum_{i \in \text{subtree}(\text{root})} \sum_{j \in \text{subtree}(\text{root})} f(i, j)$$

3. 優化：DFS 序與二維後綴和

無論是計算轉移還是計算答案，都涉及對子樹內所有節點對的雙重求和。若直接枚舉：

• 轉移：對每個 $(i, j)$，需遍歷 $i$ 和 $j$ 的所有真子孫對，單次轉移 $O(n^2)$，總計 $O(n^4)$。
• 答案：對每個查詢節點，需枚舉子樹內所有節點對，單次查詢 $O(n^2)$，總計 $O(n^3)$。

這顯然不可接受。我們利用 DFS 序將子樹映射為連續區間，從而將求和轉化為矩形區域查詢：

記號	意義
$\text{dfn}_i$	節點 $i$ 的 DFS 序編號
$\text{sz}_i$	節點 $i$ 的子樹大小
$[\text{dfn}_i, \text{dfn}_i + \text{sz}_i - 1]$	節點 $i$ 的子樹區間
$[\text{dfn}_i + 1, \text{dfn}_i + \text{sz}_i - 1]$	節點 $i$ 的真子孫區間

如此，轉移中的雙重求和等價於在二維矩陣上查詢矩形區域的 $f$ 值總和。我們維護二維後綴和陣列：

$$\text{suf}[i][j] = \displaystyle\sum_{i^{\prime} \ge i} \sum_{j^{\prime} \ge j} f(i^{\prime}, j^{\prime})$$

藉由排容原理(Principle of Inclusion-Exclusion)，矩形區域和可在 $O(1)$ 內求得。

複雜度分析

• 時間複雜度：$\mathcal{O}(n^2)$。雙層迴圈枚舉所有節點對，每次操作 $O(1)$。
• 空間複雜度：$\mathcal{O}(n^2)$。用於儲存二維後綴和陣列。

---

Code

MOD = 998244353

def solve():
    n = int(input())
    s = input().strip()

    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(lambda x: int(x) - 1, input().split())
        g[u].append(v)
        g[v].append(u)

    dfn = [0] * n
    sz = [1] * n
    order = []
    time = 0
    def dfs(u, fa):
        nonlocal time
        # dfn1[u] = time
        # order.append(u)
        # time += 1
        # for v in g[u]:
        #     if v == fa:
        #         continue
        #     dfs(v, u)
        #     sz[u] += sz[v]
        st = [(u, fa, 0)]
        while st:
            u, fa, i = st.pop()
            if i == 0:
                dfn[u] = time
                order.append(u)
                time += 1
            if i > 0:
                v = g[u][i - 1]
                sz[u] += sz[v]
            for j in range(i, len(g[u])):
                v = g[u][j]
                if v == fa:
                    continue
                st.append((u, fa, j + 1))
                st.append((v, u, 0))
                break
    dfs(0, -1)

    # suf[i][j] = sum(f[i][j] for i in [i, n) for j in [j, n))
    suf = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        u = order[i]
        r1 = i + sz[u]
        for j in range(n - 1, -1, -1):
            v = order[j]
            r2 = j + sz[v]
            # if s[u] == s[v], f[i][j] = 1 + sum(f[i][j] for i in [i+1, r1) for j in [j+1, r2))
            # where [i+1, r1) is the proper descendants of u and [j+1, r2) is the proper descendants of v
            if s[u] == s[v]:
                f = (1 + suf[i + 1][j + 1] - suf[r1][j + 1] - suf[i + 1][r2] + suf[r1][r2]) % MOD
            # else, f[i][j] = 0
            else:
                f = 0
            # suf[i][j] = f[i][j] + suf[i+1][j] + suf[i][j+1] - suf[i+1][j+1]
            suf[i][j] = (f + suf[i + 1][j] + suf[i][j + 1] - suf[i + 1][j + 1]) % MOD

    ans = [0] * n
    for u in range(n):
        l, r = dfn[u], dfn[u] + sz[u]
        ans[u] = (suf[l][l] - suf[r][l] - suf[l][r] + suf[r][r]) % MOD
    print(*ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

---

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, in the style of fashion photography, dynamic, dynamic force picture, (Visual impact:1.2), impactful picture, extreme aesthetic, A shot with tension, sharp focus, The Ninth Art, depth of field, cinematic lighting, light particles, lens flare, movie perspective, (Tyndall Effect:1.4), light particles, light, shadow, scenery, temperate atmosphere, (artist:pigeon666:0.83), (Yomu:0.4), (remsrar:0.45), (quasarcake:0.3),

1girl, solo, Nijika Ijichi (ijichi nijika, bocchi the rock), brown eyes, blonde hair, long hair, very long hair, bangs, side ponytail, school uniform, white shirt, pleated skirt, long sleeves, bow, ahoge, sidelocks, outdoors, collared shirt, bowtie, black skirt, bag, red bow, red bowtie,

holding umbrella, transparent umbrella, rain, raining, night, wet street, puddle, reflection, glowing vending machine, backlighting, neon lights, urban scenery, wide shot, landscape, horizontal, looking at viewer, blush