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

🔗 ABC438F Sum of Mex

Problem Statement

題目簡述

給一棵有 $N$ 個點的樹，點號為 $0,1,\dots,N-1$ 。

對任意一對端點 $(i,j)$ ，令 $f(i,j)$ 為路徑 $i \to j$ 沒有包含到的最小點號；若這條路徑包含了所有點，則令 $f(i,j)=N$ 。

請求出所有 $0 \le i \le j < N$ 的 $f(i,j)$ 總和。

Constraints

約束條件

$2 \le N \le 2 \times 10^5$
$0 \le u_i < v_i < N$
圖是一棵樹
輸入皆為整數

思路：貢獻轉換與鏈的動態維護

核心想法：不要直接算 mex 等於多少，而是算 mex 至少多少

對一條路徑而言，假設它的 mex 是 $m$ ，這意味著：

路徑上包含 $0, 1, \dots, m-1$
路徑上不包含 $m$

這條路徑對答案的貢獻是 $m$ 。我們可以將貢獻 $m$ 拆解為：

m = \sum_{x=1}^{N} [m \ge x]

根據前面的拆解，所有路徑的 mex 總和可以寫成：

\sum_{\text{路徑}} m = \sum_{\text{路徑}} \sum_{x=1}^{N} [m \ge x]

交換加總順序後得到：

\sum_{x=1}^{N} \left( \sum_{\text{路徑}} [m \ge x] \right)

而「 $\text{mex} \ge x$ 」等價於「這條路徑包含所有點 $0, 1, \dots, x-1$ 」。
因此，若令 $g(x)$ 為「包含所有點 $0, 1, \dots, x-1$ 的路徑數量」，那麼所有路徑的 mex 總和即為：

\sum_{x=1}^{N} g(x)

這將問題轉化為：從小到大依序加入點，並動態維護「必須包含這些點的路徑數量」。

基礎：包含根節點的路徑數

以點 $0$ 為根。整棵樹的路徑總數為 $\frac{N(N+1)}{2}$ ，而完全落在某個子樹內的路徑必定不經過根節點。若某子樹大小為 $s$ ，其內部路徑數為 $\frac{s(s+1)}{2}$ 。

因此，包含點 $0$ 的路徑數為：

g(1) = \frac{N(N+1)}{2} - \sum_{c} \frac{s_c(s_c+1)}{2}

維護必要點構成的鏈

要求路徑同時包含點 $0, 1, \dots, x-1$ 時，這些點在樹上的最小連通子圖必須是一條鏈，否則無任何簡單路徑能覆蓋。初始時鏈僅含點 $0$ ，兩端點重合。

依序加入點 $x$ ，有兩種情形：

情況一：新點已在鏈上

之前延伸其他點時已順便將其納入，鏈不變， $g(x+1) = g(x)$ 。

情況二：新點不在鏈上

從新點向父節點方向走，直到首次碰到鏈上的點。

檢查接入點的位置

第一次碰到的點，就是新點接入目前鏈的位置。

接入點是鏈的端點：可以將鏈往外延長至新點，更新端點即可。
接入點是鏈的內部點：這會在該點產生分叉，使得最小連通子圖變成度數為 3 的星狀結構。這意味著之後不可能存在任何簡單路徑能同時包含這些點，此時 $g(x+1) = g(x+2) = \dots = g(N) = 0$ ，可以直接結束計算。

計算包含當前鏈的路徑數

鏈成功延伸後（或確定不變），需要計算涵蓋當前鏈的路徑數量。

一條路徑若要覆蓋整條鏈，其兩端必須分別落在鏈的兩側之外：

非根端點：該側必須以端點的子樹內某點結束，可選點數即為端點的子樹大小。
根端點（點 $0$ ）：該側不能落在已被鏈佔用方向的子樹內。因此每當鏈從根向外延伸時，直接將根的「子樹大小」扣除該方向子樹的大小，根的剩餘大小即為該側可選點數。

實作技巧

直接修改根節點的子樹大小，讓它由「 $N$ 」逐漸變成「根側剩餘可選點數」。此後無論哪端是根節點，兩端子樹大小的乘積就是當前涵蓋鏈的路徑總數，不需要額外變數維護根側狀態。

複雜度分析

時間複雜度： $\mathcal{O}(N)$
空間複雜度： $\mathcal{O}(N)$

Code

import sys

sys.setrecursionlimit(int(3e5))


def main():
    n = int(input())
    g = [[] for _ in range(n)]

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

    pa = [-1] * n
    sz = [1] * n

    def dfs(u, fa):
        pa[u] = fa
        for v in g[u]:
            if v == fa:
                continue
            dfs(v, u)
            sz[u] += sz[v]

    dfs(0, -1)

    # g(1)：路徑包含點 0 的數量
    # 全部路徑數量是 N * (N + 1) // 2
    # 不經過 0 的路徑，一定完全在 0 的某個兒子子樹中
    ans = n * (n + 1) // 2
    for v in g[0]:
        ans -= sz[v] * (sz[v] + 1) // 2

    # vis[x] 表示 x 是否已經在目前維護的路徑上
    vis = [False] * n
    vis[0] = True

    L = R = 0  # 目前維護的最小路徑兩端點
    for x in range(1, n):
        # 如果 x 已經在目前路徑上，新增 x 不會改變條件
        if vis[x]:
            ans += sz[L] * sz[R]
            continue

        # 從 x 往上跳，直到遇到目前路徑上的點 y
        vis[x] = True
        v = x
        while not vis[pa[v]]:
            vis[pa[v]] = True
            v = pa[v]
        y = pa[v]

        # 如果 y 不是目前路徑端點，表示接到路徑中間，會產生分叉
        # 之後不可能存在包含所有 0..x 的簡單路徑
        if y != L and y != R:
            break

        # y 是端點，可以把端點延伸成 x
        if y == L:
            L = x
        else:
            R = x

        # 如果是從根 0 往某個方向延伸，
        # 那麼根這一側能選的端點數量要扣掉 child 這棵子樹
        if y == 0:
            sz[0] -= sz[v]

        # 目前路徑端點是 L, R
        # 可以選的總路徑數量就是兩側大小相乘
        ans += sz[L] * sz[R]

    print(ans)


if __name__ == "__main__":
    main()