大家好，歡迎閱讀周末演算法題專題。

今天選擇的演算法題來源於昨天同一套題中的D題，這題全場通過的人數在2600人左右。雖然通過的人數更少了一些，但是題目的難度卻並沒有增加很多，但是趣味度增加了。我也是第一次遇見這樣的問題。

題目鏈接：//codeforces.com/contest/1405/problem/D

廢話不多說，我們一起來看這題的題意。

題意

我們都知道數據結構當中的樹有這樣一個性質，如果樹當中有n個點，那麼它應該由n-1條無向邊組成。並且樹當中是一定沒有環的，如果有環的話n-1條邊就不夠了。

今天是說有兩個人分別叫做Alice和Bob在一棵樹上玩遊戲，這兩個人名是業內的慣例。凡是兩個人玩遊戲的題目，主人公的名字很多都叫Alice和Bob，我也不知道這個慣例的由來，大家知道這麼回事就好了。Alice和Bob兩人各自佔據了樹上的一個點，然後兩個人交替移動。Alice先手，Bob後手。

Alice每一次移動最多可以移動da距離，Bob最多可以移動db距離，兩個人也可以放棄移動。假設兩人都絕頂聰明每一次都會選擇最佳策略，請問經過最多個回合之後，Alice能否捉到Bob呢？如果可以則Alice獲勝，否則Bob獲勝。注意在Bob的回合，它可以經過Alice的節點，這並不會被視為捉到。

不知道為什麼看到這道題的時候，總是會想起費玉清的段子，不知道你們有沒有這種感覺。

樣例

第一行輸入一個數t，表示測試數據的組數。

對於每組數據首先有5個數，分別是n, a, b, da, db。n表示樹節點的個數，a和b表示遊戲開始時a和b出生點的位置。da和db表示Alice和Bob每回合最多移動的距離。這幾個數的最大範圍都是，並且多組數據當中所有的n相加不超過。

我們來看兩組樣例：

4 3 2 1 2
1 2
1 3
1 4
6 6 1 2 5
1 2
6 5
2 3
3 4
4 5

第一組數據是這樣的：

藍色表示Alice，紅色是Bob。由於Alice先手，只要Alice移動到1節點，無論Bob如何移動，他都必輸無疑。

第二組數據：

由於Alice最多只能移動兩格，第一回合移動到3，Bob選擇不動。只要Alice移動，不論是一格還是兩格，Bob都可以直接移動到1節點。也就是說最終Bob就在1和6節點之間來回移動，躲開Alice的追捕。

題解

看到Alice和Bob兩人遊戲，並且兩人都絕頂聰明會選擇最佳策略，首先想到的就是博弈論。但是觀察一下你會發現這題和博弈論沒有什麼關係，因為博弈論往往都是公平博弈，局面會有狀態轉移。但這題當中不是，這題不存在勝負狀態轉移，一定會有一個確定的結果，就是是誰勝誰負，所以這題不滿足博弈論的前提。

類似博弈論的題面只是障眼法而已，如果你信了，並且真的往這方面努力，那麼你就被出題人騙了。不過這個陷阱還是比較明顯的，很容易看出來。接下來我們又遇到了另外一個陷阱，這個陷阱也很明顯，就是執行的回合數量。題目給的是，這個數是真正的天文數字，比宇宙當中所有的粒子數都要多。所以我們可以完全可以理解成無限遊戲。

如果出題人陰險一點，完全可以給一個這個量級的回合數，會更有欺騙性一些。其實我們想一下就會發現，樹上節點最多只有個，當它們玩追逐遊戲的時候，只會有兩種情況，一種是永遠也追不上，還有一種是很快就追上。所以這個回合數沒什麼意義，就是唬人的。

洞見

首先，第一個洞見是這道題我們使用模擬是不可行的。所謂的模擬也就是模擬題意的運行情況，去一步一步地分析每一個玩家的選擇，做出最好的決策，最後得出遊戲的結果。不可行的原因也很簡單，因為會超時。這個非常明顯，就不深入解釋了。

除此之外，我們還可以得到其他一些洞見。首先第一個很簡單的洞見是，如果Alice和Bob出生的位置相距小於da的話，那麼Alice必勝。這個也很好理解，一開始的距離就在Alice的移動範圍內，那Bob一上來就被抓住了。沒有討論的餘地。另外一個洞見是如果da >= db，那麼Alice必勝。

也就是如果Bob跑得比Alice慢的話，他也一樣必敗。這也很簡單，因為地圖的範圍是有限的，一個追一個逃，逃的速度比追的慢，顯然他逃不出去。這個結論雖然簡單，但是反過來一想會得到一個問題。如果Bob跑得比Alice快的話，他一定可以獲勝嗎？

我們看第一個案例就知道這個答案不一定，因為地形也會影響最終的結果。樹意味著每一個節點都全連通，也意味著每兩點的路線只有一條。換句話說每一條路線都是思路，即使Bob跑得快如果不反向跑甩掉Alice的話，那麼他也是一樣會被Alice追上的。

所以我們接下來要做的就是深入分析這裡的情況，把剩下的問題捋清楚。

回味樣例

codeforces的問題有一個特點就是我們一定要深入分析樣例，因為很多出題人很良心，給出的樣例都是關鍵樣例。我們可以藉助樣例的情況幫助我們分析問題。比如今天說的這題就是一個。

我們來分析一下第一個樣例：

這就是典型的Bob跑得比Alice快的樣例，Bob不僅跑得比Alice快，甚至還是Alice的兩倍。但是我們都知道結果還是Alice獲勝，原因也很簡單，Alice移動到1號節點之後，Bob只有兩個選擇要麼1號節點要麼4號節點，這兩個節點都距離1號節點只有一個距離，仍然在Alice追上的範圍內。

在這個樣例當中Bob的逃跑空間勉強是夠的，但還是被追上了，說明他的逃跑速度是不夠的。不夠的原因也很簡單，因為一開始當Alice移動到1節點之後，他距離Bob的距離是1，也就是一個da。這時Bob無路可走只能折返甩開Alice，這時候他最多能夠走一個db，他要想不被Alice捉住，首先他需要先走過da這一段距離，接著他需要走出至少da+1的距離，才能保證Alice折返追他也追不到。那麼我們可以得出一個條件是db > 2da。

但我們發現僅僅db > 2da還是不夠的，因為在這個例子當中我們可以看得出來不夠開闊，即使db=3，Bob也沒處可去。也就是說在這棵樹上至少有一條鏈路它的長度要大於2da才行，否則即使Bob再能跑也會被地形限制住。對於一棵樹而言，求它的最長鏈路還是比較簡單的，我們也在之前的文章當中講解過，其實就是對於每一個節點都求一個到葉子節點的最長距離和次長距離之和。所有的節點的距離最大的那個就是整棵樹上的最長鏈路。

我們整理一下思路，一共發現了3個條件，只有滿足這3個條件，Bob才可能跑掉，否則一定會被Alice捉住。這三個條件分別是：

1. 起始的時候Bob和Alice距離大於da
2. 樹的直徑大於2da
3. db大於2da

所以我們要求的就只有兩點，第一點是一開始它們之間的距離，以及樹的直徑（樹上最長的鏈路長度）。好在這兩點都可以通過遞歸實現。都理出來了之後程式碼就不難寫了：

t = int(input())

depth = [0 for _ in range(200050)]
for _ in range(t):
    n, a, b, da, db = list(map(int, input().split(' ')))
    edges = [[] for _ in range(n+2)]
    for i in range(n-1):
        u, v = list(map(int, input().split(' ')))
        edges[u].append(v)
        edges[v].append(u)

    diameter = 0

    depth[a] = 0
    def dfs(u, f):
        global diameter
        l = 0
        for v in edges[u]:
            if v == f:
                continue
            # depth數組記錄每個節點的樹深
            depth[v] = depth[u] + 1
            cur = 1 + dfs(v, u)
            # cur + l即u節點到葉子節點的最長距離和次長距離
            # 直徑就是這兩者和之中最大的一個
            diameter = max(diameter, cur + l)
            l = max(l, cur)

        return l

 # 以Alice所在的點作為樹根，這樣depth[b]即Alice和Bob的距離
    dfs(a, -1)
    if depth[b] <= da or da * 2 >= diameter or da*2 >= db:
        print('Alice')
    else:
        print('Bob')

我們把整個思路說穿了是不是有一種一文不值的感覺？但是自己思考要想明白還是不太容易的，codeforces的問題就是這樣，經常需要我們在紙上畫一畫看一看。有時候一些點靠自己想很難完全想明白，但是找一個例子試一試一下就清楚了。這也是codeforces問題有趣的地方之一。

衷心祝願大家每天都有所收穫。如果還喜歡今天的內容的話，請來一個三連支援吧~（點贊、關注、轉發）

原文鏈接，求個關注

本文使用 mdnice 排版

– END –