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

🔗 🟢 ABC428E Farthest Vertex

Problem Statement

題目簡述

給定一棵 $N$ 個頂點的樹，對每個頂點 $v = 1, 2, \dots, N$ ，找出距離 $v$ 最遠的頂點。若有多個同距頂點，輸出編號最大的那個。

Constraints

約束條件

$2 \le N \le 5 \times 10^5$
$1 \le A_i < B_i \le N$
輸入的圖是一棵樹

思路：樹的直徑端點性質

關鍵性質：最遠點必為直徑端點

核心定理

在一棵樹中，對於任意頂點 $v$ ，距離 $v$ 最遠的頂點一定是該樹某條直徑的端點之一。

直覺理解：樹的直徑是最長的路徑，它的兩個端點 $x, y$ 代表了樹中「最極端」的兩個位置。任何頂點離得最遠的點，不可能跳出直徑端點所能覆蓋的距離範圍。

證明（反證法）

設 $x, y$ 為給定樹的直徑兩端點，因此這棵樹的直徑 $\text{diam}(T) = d(x, y)$ 。
假設存在某個頂點 $v$ ，距離它最遠的頂點 $w \notin \{x, y\}$ ，即滿足：
$d(v, w) > d(v, x)$ 且 $d(v, w) > d(v, y)$ 。

為了嚴格證明矛盾，我們將 $v$ 和 $w$ 的路徑映射（投影）到直徑 $x-y$ 上。設它們分別在 $u$ 和 $z$ 點與直徑相交（ $u$ 和 $z$ 為直徑上的頂點，且可能重合）。不失一般性，我們假設 $x, u, z, y$ 在直徑上的相對順序如下圖：

graph LR
    v(("v")) -.-|"d(v, u)"| u(("u"))
    w(("w (假想的最遠點)")) -.-|"d(w, z)"| z(("z"))
    x(("x (端點)")) ===|"d(x, u)"| u
    u ===|"d(u, z)"| z
    z ===|"d(z, y)"| y(("y (端點)"))
    
    classDef default fill:transparent,stroke:currentColor,stroke-width:2px;
    style x stroke:#f66,stroke-width:3px
    style y stroke:#f66,stroke-width:3px
    style w stroke:#66f,stroke-width:3px
    linkStyle 2,3,4 stroke-width:3px,stroke:#f88

根據圖上的路徑結構，我們來比較 $v$ 到 $w$ 和 $v$ 到 $y$ 的距離：

$d(v, w) = d(v, u) + d(u, z) + d(z, w)$
$d(v, y) = d(v, u) + d(u, z) + d(z, y)$

因為我們假設了 $w$ 是 $v$ 的最遠點，所以 $d(v, w) > d(v, y)$ 。將上方兩式代入，並消去兩邊都有的共同路徑 $d(v, u) + d(u, z)$ 後，可以得出一個極為關鍵的轉折結論：

d(z, w) > d(z, y)

這意味著，從直徑上的 $z$ 點出發，走到假想的 $w$ 的距離，居然比走到直徑端點 $y$ 還遠！

接著重點來了，我們用這個發現去檢驗另一個直徑端點 $x$ 走到 $w$ 的總距離：

d(x, w) = d(x, z) + d(z, w)

將剛才得出的 $d(z, w) > d(z, y)$ 代入：

d(x, w) > d(x, z) + d(z, y) = d(x, y)

也就是說， $d(x, w) > \text{diam}(T)$ 。我們居然在樹中算出了一條比直徑本身還要長的路徑 $x \to w$ ！這與「 $x, y$ 是直徑端點」的最根本條件產生了嚴重矛盾。

（附註：若 $u, z$ 在直徑上的相對順序相反，利用完全對稱的推導也可以精確算出 $d(y, w) > \text{diam}(T)$ ，同樣產生矛盾）

故假設不成立，對於任意節點 $v$ ，其最遠點必定是直徑的兩個端點 $x$ 或 $y$ 之一。

因此，答案對每個頂點 $v$ 只會是 $x$ 或 $y$ 之一！

演算法流程

利用上述性質，只需三次 BFS：

找直徑端點 $x$ ：從任意頂點（例如 $0$ ）做 BFS，距離最遠且編號最大者即為 $x$ 。
找直徑端點 $y$ ：從 $x$ 做 BFS，距離最遠且編號最大者即為 $y$ ；同時記錄 $\text{distx}[\cdot]$ 。
計算第三份距離：從 $y$ 做 BFS，得到 $\text{disty}[\cdot]$ 。

取完 $x, y$ 後，確保 $x > y$ （若不然則交換），這樣在距離相同時選 $x$ 就能滿足「取編號最大」的要求。

處理最大編號的細節

邊界處理

題目要求「距離相同時取編號最大的頂點」。程式碼中使用 >= 來挑選 $x$ 和 $y$ （從小編號掃到大編號，>= 會不斷更新為更大的編號），並在最後確保 $x > y$ 。這樣在 d1 >= d2 時選 $x$ 就自然滿足了最大編號的需求。

總結

樹中任意頂點的最遠點必為直徑端點之一。只需三次 BFS 求出直徑兩端 $x, y$ 及各自到所有頂點的距離，對每個頂點取距離較大的端點即為答案。整體 $\mathcal{O}(N)$ 。

複雜度分析

時間複雜度： $\mathcal{O}(N)$ （三次 BFS，每次 $\mathcal{O}(N)$ ）
空間複雜度： $\mathcal{O}(N)$ （鄰接表 + 距離陣列）

Code

from collections import deque


def solve():
    n = int(input())
    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)

    def bfs(st: int) -> list[int]:
        dist = [float("inf")] * n
        dist[st] = 0
        q = deque([st])
        while q:
            u = q.popleft()
            for v in g[u]:
                if dist[v] == float("inf"):
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist

    # BFS/DFS 求直徑，但需要取編號較大的點
    dist = bfs(0)
    x = -1
    for u in range(n):
        if dist[u] >= dist[x]:
            x = u
    distx = bfs(x)
    y = -1
    for u in range(n):
        if distx[u] >= distx[y]:
            y = u
    disty = bfs(y)

    # 確保 x 的編號比 y 的編號大
    if x < y:
        x, y = y, x
        distx, disty = disty, distx

    ans = []
    for u in range(n):
        d1 = distx[u]
        d2 = disty[u]
        # 距離 u 最遠的點一定是直徑上的端點之一
        ans.append(x + 1 if d1 >= d2 else y + 1)
    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()