l254. B - 尼姆樹 - 高中生程式解題系統

內容

給你 $N$ 個點、帶邊權的樹，節點編號為 $1 \sim N$ ，有兩個人要在這圖上玩遊戲，一開始起點在 $1$ ，起點上面放了一個棋子，兩個人輪流進行操作，每一個操作是選擇任何一個在棋子目前位置周遭邊權 $> 0$ 的邊，把棋子移到邊上另一頭的點，並選擇任何小於等於該邊邊權的正整數 $x$ ，把剛剛經過的邊權減少 $x$ ，不停輪流操作直到某一方無法進行任何操作結束，我們定義進行最後一個操作的人獲勝。

請問，如果兩個人使用最佳策略，那最終是誰會獲勝? 如果是第一個人獲勝輸出 First，反之輸出 Second，另外我們可以證明這個遊戲在有限局數內一定會結束。

輸入說明

輸入第一行有個正整數 $N$ ，代表這棵樹的節點數量。

接著有 $N - 1$ 行，每行三個數 $U_{i}, V_{i}, W_{i}$ ，中間以空白隔開，這些數字代表點 $(U_{i}, V_{i})$ 中間有個權重 $W_{i}$ 的邊。

$2 \leq N \leq 10^{5}$
$1 \leq U_{i}, V_{i} \leq N, U_{i} \neq V_{i}$
$1 \leq W_{i} \leq 10^{9}$
保證輸入是一棵樹

輸出說明

輸出一行表示答案。 (First或Second)

範例輸入 #1

範例輸出 #1

First

範例輸入 #2

範例輸出 #2

Second

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 1.0s , <1K
不公開測資點#1 (5%): 1.0s , <1K
不公開測資點#2 (5%): 1.0s , <1K
不公開測資點#3 (5%): 1.0s , <1K
不公開測資點#4 (5%): 1.0s , <1K
不公開測資點#5 (5%): 1.0s , <1K
不公開測資點#6 (5%): 1.0s , <1K
不公開測資點#7 (5%): 1.0s , <1K
不公開測資點#8 (5%): 1.0s , <1K
不公開測資點#9 (5%): 1.0s , <1K
不公開測資點#10 (5%): 1.0s , <1M
不公開測資點#11 (5%): 1.0s , <1M
不公開測資點#12 (5%): 1.0s , <1M
不公開測資點#13 (5%): 1.0s , <1M
不公開測資點#14 (5%): 1.0s , <10M
不公開測資點#15 (5%): 1.0s , <10M
不公開測資點#16 (5%): 1.0s , <10M
不公開測資點#17 (5%): 1.0s , <10M
不公開測資點#18 (5%): 1.0s , <10M
不公開測資點#19 (5%): 1.0s , <10M

提示：

範例輸入 # 1

以下為輸入內容畫成圖的樣子 :

以下為一種遊玩的過程 (用 F、S 代表 First、Second) :

F : 棋子目前在 $1$ ，把棋子移動到 $2$ ，並選擇把邊 $(1, 2)$ 的邊權減少 $1$ 。

S : 棋子目前在 $2$ ，把棋子移動到 $7$ ，並選擇把邊 $(2, 7)$ 的邊權減少 $1$ 。

F : 棋子目前在 $7$ ，把棋子移動到 $2$ ，並選擇把邊 $(2, 7)$ 的邊權減少 $2$ ，注意邊 $(2, 7)$ 這時的邊權變成 $0$ ，所以這條邊以後不能再被經過。

S : 棋子目前在 $2$ ，把棋子移動到 $1$ ，並選擇把邊 $(1, 2)$ 的邊權減少 $1$ ，注意邊 $(1, 2)$ 這時的邊權變成 $0$ ，所以這條邊以後不能再被經過。

F : 棋子目前在 $1$ ，把棋子移動到 $5$ ，並選擇把邊 $(1, 5)$ 的邊權減少 $1$ ，注意邊 $(1, 5)$ 這時的邊權變成 $0$ ，所以這條邊以後不能再被經過。

S 無法做任何操作，故答案為 First。

Authored by r1cky

標籤:

出處:

第一屆Chi怪壓常比賽 [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
36777	r1cky (hehe)	l254		265	2023-08-08 10:10