P11902 [NHSPC 2023] A. 演化樹分析

彼得是一位生物學家。有次他在兩筆資料中分析同一群現存物種集合 $\Sigma = \{1, 2, \ldots, n\}$ 間的演化關係，卻得到了不太一樣的演化樹，想知道這兩棵演化樹的類似程度。 一棵演化樹 $T$ 是一棵無向無根樹 (undirected, unrooted tree)，其中葉節點為現存物種 $1, 2, \ldots, n$，其他節點則為已滅絕物種。設 $v \in V(T)$，我們用 $\deg(v)$ 來表示與節點 $v$ 相鄰的節點個數。在一棵演化樹中，每個代表已滅絕物種的節點 $v$ 均有 $\deg(v) \ge 3$。對於一個現存物種的子集合 $X \subseteq \Sigma$，我們用 $T\{X\}$ 來代表 $X$ 中的現存物種在 $T$ 上的演化關係所形成的「演化子樹」，建構方式如下： 1. 對所有 $X$ 中的任兩點，標記其在 $T$ 上的簡單路徑，並將所有不在 $X$ 且未被標記的點刪除以得到 $T'$。 1. 從 $T'$ 中不斷刪除滿足 $\deg(v) = 2$ 的非葉節點 $v$ 以得到 $T\{X\}$：將與 $v$ 連結的兩條邊合併成一條，並移除 $v$。 以下圖的演化樹 $T$ 為例。$T$ 裡的現存物種集合為 $\Sigma = \{1, 2, 3, 4, 5\}$，若取 $X = \{3, 4, 5\}$，則經步驟 $1$ 後會得到 $T'$，再經過步驟 $2$ 後會得到 $T\{X\}$。注意當 $X = \emptyset$ 時，根據定義我們有 $T\{X\} = \emptyset$。  從一棵演化樹 $T$ 中移除大小為 $k \ge 0$ 的任意邊集合 $K$，可以得到 $k+1$ 棵子樹 $T^{(1)}, T^{(2)}, \ldots, T^{(k+1)}$，其中每棵子樹 $T^{(i)}$ 上的物種在 $T$ 中的演化關係都會構成一棵**演化子樹**，我們稱它們為從 $T$ 中移除 $K$ 所導出的**演化森林**。注意我們有 1. $T$ 自身為移除 $\emptyset$ 後導出的演化森林。 1. 若一棵子樹 $T^{(i)}$ 上沒有任何現存物種，對應的演化子樹為空。 以上圖中的 $T$ 為例，移除 $K = \{(1, 7), (7, 8), (2, 8), (5, 8)\}$ 四條邊可以得到五棵子樹 $T^{(1)}, T^{(2)}, \ldots, T^{(5)}$，接著導出演化森林：  比較兩座現存物種相同的演化森林時，我們只關注現存物種間的關係，因此已滅絕物種（即非葉節點）的編號並不重要。設 $F_1$ 與 $F_2$ 為兩座現存物種相同的演化森林，若移除它們的非葉節點編號後變得完全相同，我們就稱 $F_1$ 與 $F_2$ 類似。更精確地說，我們稱 $F_1$ 與 $F_2$ 類似，若且唯若存在某個一對一函數 $\Phi: V(F_1) \to V(F_2)$，滿足 1. 對任意 $u \in \Sigma = \{1, 2, \ldots, n\}$，我們有 $\Phi(u) = u$。 1. 對任意 $u, v \in V(F_1)$，我們有 $$(u, v) \in E(F_1) \iff (\Phi(u), \Phi(v)) \in E(F_2).$$ 以下圖為例，如果將 $T_1, T_2, T_3$ 的非葉節點編號都移除，會發現 $T_1$ 與 $T_2$ 不類似，而 $T_2$ 與 $T_3$ 類似。  設 $T_1$ 與 $T_2$ 為現存物種相同的兩棵演化樹。若存在從 $T_1$ 與 $T_2$ 中各刪除 $k$ 條邊的方法，使得兩者導出的演化森林類似，則稱 $T_1$ 與 $T_2$ 的差異不大於 $k$，而滿足此條件的最小整數 $k^*$ 稱為 $T_1$ 與 $T_2$ 的**差異數**。如上圖中 $T_2$ 與 $T_3$ 的差異數為 $0$，而 $T_1$ 與 $T_2$ 的差異數為 $1$。  從 $T_1$ 與 $T_2$ 各刪除 $1$ 條邊 | 導出了類似的演化森林 設從 $T_1$ 與 $T_2$ 中刪除的邊集合分別為 $K_1$ 與 $K_2$，兩種刪除方法被視為不同若且唯若 $K_1$ 不同或 $K_2$ 不同。現給定兩棵物種集合均為 $\Sigma$ 的演化樹 $T_1, T_2$ 以及一個整數上限 $k$，彼得想知道它們的差異數 $k^*$ 是否不大於 $k$；如果 $1 \le k^* \le k$，彼得也想知道有多少種從 $T_1$ 和 $T_2$ 中各刪除 $k^*$ 條邊的方法，可以使它們導出類似的演化森林。

> $n$ $m_1$ $m_2$ $k$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_{n+m_1-1}$ $v_{n+m_1-1}$ > $u_1'$ $v_1'$ > $u_2'$ $v_2'$ > $\vdots$ > $u_{n+m_2-1}'$ $v_{n+m_2-1}'$ * $n$ 代表現存物種集合 $\Sigma = \{1, 2, \ldots, n\}$ 的大小。 * $m_1$ 代表在 $T_1$ 中已滅絕物種（以 $n+1, n+2, \ldots, n+m_1$ 表示）的數量。 * $m_2$ 代表在 $T_2$ 中已滅絕物種（以 $n+1, n+2, \ldots, n+m_2$ 表示）的數量。 * $k$ 代表彼得設定的上限。 * $u_i, v_i$ 代表 $T_1$ 有一條邊從 $u_i$ 連接到 $v_i$。 * $u_i', v_i'$ 代表 $T_2$ 有一條邊從 $u_i'$ 連接到 $v_i'$。

如果 $k^* = 0$，請輸出 > $0$ 如果 $1 \le k^* \le k$，請輸出 > $k^*$ > $S$ 其中 $S$ 為一整數，代表從 $T_1$ 與 $T_2$ 中各刪除 $k^*$ 條邊後導出的演化森林類似的刪除方法數。如果 $k^* > k$，請輸出 > $-1$

### 測資限制 * $n \ge 2$。 * $0 \le m_1 \le 300-n$。 * $0 \le m_2 \le 300-n$。 * $k \in \{0, 1, 2\}$。 * $1 \le u_i \le n+m_1$。 * $1 \le v_i \le n+m_1$。 * $1 \le u_i' \le n+m_2$。 * $1 \le v_i' \le n+m_2$。 * 給定的 $T_1$ 與 $T_2$ 保證連通，且 1. 若 $u \in \{1, 2, \ldots, n\}$，則在 $T_1$ 與 $T_2$ 中 $\deg(u) = 1$。 1. 若 $u \in \{n+1, n+2, \ldots, n+m_1\}$，則在 $T_1$ 中 $\deg(u) \ge 3$。 1. 若 $u \in \{n+1, n+2, \ldots, n+m_2\}$，則在 $T_2$ 中 $\deg(u) \ge 3$。 * 輸入的數皆為整數。 ### 評分說明 本題共有四組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。 | 子任務 | 分數 | 額外輸入限制 | | :------: | :----: | ------------ | | 1 | $21$ | $k = 0$ | | 2 | $13$ | $k \in \{0, 1\}$ | | 3 | $23$ | $n+m_1 \le 30$ 且 $n+m_2 \le 30$ | | 4 | $43$ | 無額外限制 |