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

🔗 CF2178F Conquer or of Forest

rating: 2232

Problem Statement

題目簡述

給定一棵以節點 $1$ 為根、 $n$ 個節點的樹。根據子樹大小的奇偶性對節點著色：偶數為白色，奇數為黑色。

操作：選擇一個非根的白色節點 $w$ ，斷開 $(w, \text{parent}(w))$ 邊，在保持樹的結構的前提下，在任意兩點間加一條新邊，然後根據子樹大小的奇偶性重新著色。

目標：使所有白色節點都位於從根到某節點的路徑上（或不存在白色節點）。

求透過任意次操作能構造的不同「目標樹」數量，答案對 $998244353$ 取模。

Constraints

約束條件

每棵樹的節點數 $n$ （ $2 \le n \le 2 \times 10^5$ ）
保證輸入是一棵樹

思路：計數

關鍵觀察：斷開白點形成連通分量

白點的性質

白色節點的子樹大小為偶數。因此，如果我們斷開所有白色節點 $w$ 與其父節點 $p_w$ 之間的邊，整棵樹會被切分成若干個連通分量。

設總共形成 $k + 1$ 個連通分量： $S_0, S_1, S_2, \ldots, S_k$ ，其中：

$S_0$ 是包含根節點 $1$ 的連通分量
$S_1, S_2, \ldots, S_k$ 是其餘 $k$ 個連通分量

連通分量的固定性質

固定性質

無論執行多少次操作，對於 $S_0$ 以外的連通分量而言，這些連通分量的大小始終保持不變，且每個連通分量內恰好有一個白色節點，該白點是連通分量中距離根最近的節點。

為什麼連通分量的大小不會改變？

黑色節點的父邊不能被移除：操作只能選擇白色節點來斷邊，因此黑色節點與其父節點之間的邊永遠不會被切斷。
連通分量內部結構固定：由於連通分量內除了根（白點）以外都是黑點，而黑點的父邊不可移除，所以連通分量內部的邊結構是不變的。
顏色會自動調整：每個連通分量的大小為偶數（因為白點的子樹大小為偶數）。當連通分量被重新連接到樹中時，距離根最近的那個節點會自動變成白色。

目標條件的轉化

目標

要讓所有白色節點都在從根到某一點的簡單路徑上，實際上我們需要把所有連通分量串成一條單鏈：

S_0 \to S_{p_1} \to S_{p_2} \to \cdots \to S_{p_k}

這條鏈不能有分叉，否則就會有兩個白色節點不在同一條從根出發的路徑上。

連接方案數的計算

當我們要把連通分量 $S_B$ 接在連通分量 $S_A$ 下面時：

在 $S_A$ 中選一個節點 $u$ （有 $|S_A|$ 種選擇）。
在 $S_B$ 中選一個節點 $v$ （有 $|S_B|$ 種選擇）。
連邊 $(u, v)$ 。此時 $v$ 成為 $S_B$ 連通分量在當前樹中的新根，而 $S_B$ 整體大小為偶數，所以 $v$ 變白。

因此，將連通分量 $S_B$ 接到 $S_A$ 上的方案數是 $|S_A| \times |S_B|$ 。

推導總方案數

假設我們選定的排列順序是 $S_0 \to S_{p_1} \to S_{p_2} \to \cdots \to S_{p_k}$ ，連接方案數為：

|S_0| \times |S_{p_1}|^2 \times |S_{p_2}|^2 \times \cdots \times |S_{p_{k-1}}|^2 \times |S_{p_k}|

又因為 $\left(\prod_{i=1}^{k} |S_{p_i}|\right) = \left(\prod_{i=1}^{k} |S_i|\right)$ ，我們可以把式子改寫成：

|S_0| \times \left(\prod_{i=1}^{k} |S_i|^2\right) \times \frac{1}{|S_{p_k}|}

我們需要對 $S_1, \ldots, S_k$ 的所有 $k!$ 種排列求和。考慮哪個連通分量在鏈尾：假設 $S_j$ 在鏈尾，那麼剩下的 $k-1$ 個連通分量有 $(k-1)!$ 種排列方式。因此總答案為：

\sum_{j=1}^{k} \left[(k-1)! \times |S_0| \times \left(\prod_{i=1}^{k} |S_i|^2\right) \times \frac{1}{|S_j|}\right]

提出與 $j$ 無關的因子後：

|S_0| \times (k-1)! \times \left(\prod_{i=1}^{k} |S_i|^2\right) \times \left(\sum_{j=1}^{k} \frac{1}{|S_j|}\right)

最終公式

\text{ans} = |S_0| \times (k-1)! \times \left(\prod_{i=1}^{k} |S_i|^2\right) \times \left(\sum_{j=1}^{k} |S_j|^{-1}\right) \pmod{998244353}

特殊情況

k = 0

的情況

當 $k = 0$ 時，只有連通分量 $S_0$ ，表示沒有除了根節點之外的白色節點。此時樹已滿足目標條件，且不存在可以操作的連通分量，答案為 $1$ 。

複雜度分析

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

Code

from functools import reduce

MOD = 998244353

MAX_N = int(2e5 + 5)
fact = [1] * (MAX_N + 1)
for i in range(1, MAX_N + 1):
    fact[i] = (fact[i - 1] * i) % MOD

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)

    comps = []
    sz = [0] * n
    def dfs(u, fa):
        # sz[u] = 1
        # for v in g[u]:
        #     if v == fa:
        #         continue
        #     dfs(v, u)
        #     if sz[v] & 1:
        #         sz[u] += sz[v]
        #     else:
        #         comps.append(sz[v])
        st = [(u, fa, 0)]
        while st:
            u, fa, i = st.pop()
            if i == 0:
                sz[u] = 1
            if i > 0:
                v = g[u][i - 1]
                if sz[v] & 1:
                    sz[u] += sz[v]
                else:
                    comps.append(sz[v])
            for j in range(i, len(g[u])):
                v = g[u][j]
                if v == fa:
                    continue
                st.append((u, fa, j + 1))
                st.append((v, u, 0))
                break
    dfs(0, -1)
    
    if len(comps) == 0:
        print(1)
        return

    ans = (sz[0] * fact[len(comps) - 1]) % MOD
    ans = (ans * reduce(lambda x, y: (x * y * y) % MOD, comps, 1)) % MOD
    ans = (ans * reduce(lambda x, y: (x + y) % MOD, map(lambda x: pow(x, MOD - 2, MOD), comps), 0)) % MOD
    print(ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()