📌 點擊直達筆試專欄 👉《大廠筆試突圍》

💻 春秋招筆試突圍在線OJ 👉 筆試突圍OJ

03. 奇偶平衡樹分割問題

問題描述

K小姐是一位園林設計師，她設計了一個由多個花壇組成的樹形公園。每個花壇中種植了不同數量的花，數量由整數表示。K小姐發現，當公園被分割成多個獨立區域時，如果每個區域中的花朵總數都是偶數，游客會感到更加和諧。

現在，K小姐想要通過關閉若干條連接花壇的小路（即刪除樹的邊），將公園分割成若干個獨立區域（連通塊），使得每個區域內的花朵總數都是偶數。

請你求出，對于每個 $k(1\le k\le n?1)$，關閉 $k$ 條小路后得到的 $k+1$ 個獨立區域滿足條件的方案數。如果不存在滿足條件的方案，對應的答案記為 $0$。

注意：兩種關閉小路的方案若關閉的路徑集合不同，則視為不同的方案。

輸入格式

第一行給出一個整數 $n$，表示花壇的數量。

第二行給出 $n$ 個整數 $W_1,W_2,...,W_n$，其中 $W_i$ 表示第 $i$ 個花壇中的花朵數量。

接下來 $n?1$ 行，每行包含兩個整數 $u$ 與 $v(1\le u,v\le n,u\ne v)$，表示花壇 $u$ 與花壇 $v$ 之間有一條小路，保證給定的圖構成一棵樹。

輸出格式

輸出 $n?1$ 個數，第 $i$ 個數表示關閉 $i$ 條小路后滿足條件的方案數。由于答案可能非常大，請對答案取模 $10^9+7$ 后輸出。

樣例輸入

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

樣例輸出

3 3 1 0

樣例	解釋說明
樣例1	當 $k=1$ 時，關閉方案有 {(1,2)}, {(2,4)}, {(2,5)}，共 3 種。 當 $k=2$ 時，關閉方案有 {(1,2), (2,4)}, {(1,2), (2,5)}, {(2,5), (2,4)}，共 3 種。 當 $k=3$ 時，關閉方案有 {(1,2), (2,4), (2,5)}，共 1 種。 當 $k=4$ 時，沒有滿足條件的方案。

數據范圍

• $2\le n\le 10^5$
• $1\le W_i\le 10^9$
• $1\le u,v\le n$

題解

這道題乍看復雜，但仔細分析后會發現其中的數學規律和解決方案。

首先，我們需要理解什么情況下一個連通塊的花朵數能夠為偶數。顯然，如果一個連通塊內奇數花壇的個數為偶數，那么總花朵數一定是偶數（偶數+偶數=偶數，奇數+奇數=偶數）。

我們的目標是通過刪除邊，將樹分成多個連通塊，使得每個連通塊內的奇數花壇數量都是偶數。那么問題轉化為：找出那些刪除后能讓兩側奇數花壇數量都是偶數的邊。

關鍵觀察：一個連通塊內奇數花壇數量為奇數時，無論如何分割，都無法使所有子連通塊內的奇數花壇數量都為偶數。因為奇數個奇數，無論如何分組，總有一組含有奇數個奇數。

因此，如果整棵樹中奇數花壇的總數為奇數，則無解。

接下來，我們定義一個邊是"好邊"，如果刪除這條邊后，兩個連通塊內的奇數花壇數量都是偶數。一條邊是好邊當且僅當這條邊連接的子樹內奇數花壇數量為偶數。

如果好邊數量為g，那么要刪除k條邊使所有連通塊花朵數為偶數，就相當于從g條好邊中選擇k條，即組合數C(g,k)。

具體算法如下：

1. 統計整棵樹中奇數花壇的總數，如果為奇數，則無解。
2. 通過DFS計算每個子樹中奇數花壇的數量。
3. 檢查每條邊，如果刪除后兩側連通塊中奇數花壇數量都是偶數，則該邊為好邊。
4. 計算從g條好邊中選k條的組合數C(g,k)，即為答案。

時間復雜度分析：

• DFS遍歷樹的復雜度為O(n)
• 檢查每條邊的復雜度為O(n)
• 計算組合數的復雜度為O(n)
  總體時間復雜度為O(n)，空間復雜度為O(n)。

參考代碼

• Python

import sys
input = lambda: sys.stdin.readline().strip()def solve():# 讀取輸入n = int(input())w = [0] + list(map(int, input().split()))adj = [[] for _ in range(n+1)]for _ in range(n-1):u, v = map(int, input().split())adj[u].append(v)adj[v].append(u)# 計算奇數花壇的總數odd_count = sum(1 for val in w[1:] if val % 2 == 1)# 如果奇數花壇總數為奇數，則無解if odd_count % 2 == 1:print(" ".join(["0"] * (n-1)))return# 計算子樹中奇數花壇的數量t = [0] * (n+1)good_edges = 0# DFS計算子樹信息def dfs(node, parent):nonlocal good_edgesis_odd = w[node] % 2  # 當前節點是否為奇數for child in adj[node]:if child != parent:# 遞歸計算子樹dfs(child, node)# 更新當前節點的奇數計數is_odd ^= t[child]t[node] = is_odd# 檢查是否為好邊if parent != 0 and t[node] == 0:good_edges += 1# 從根節點開始DFSdfs(1, 0)# 計算組合數MOD = 10**9 + 7# 預計算階乘和逆元fact = [1] * (n+1)inv_fact = [1] * (n+1)for i in range(1, n+1):fact[i] = (fact[i-1] * i) % MOD# 計算逆元（使用費馬小定理）def pow_mod(x, p):res = 1while p > 0:if p & 1:res = (res * x) % MODx = (x * x) % MODp >>= 1return resinv_fact[n] = pow_mod(fact[n], MOD - 2)for i in range(n, 0, -1):inv_fact[i-1] = (inv_fact[i] * i) % MOD# 計算組合數C(n,k)def comb(n, k):if k < 0 or k > n:return 0return (fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD)# 計算并輸出結果result = []for k in range(1, n):ans = comb(good_edges, k)result.append(str(ans))print(" ".join(result))if __name__ == "__main__":solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;// 快速冪計算a^b mod MOD
ll pow_mod(ll a, ll b) {ll res = 1;while (b > 0) {if (b & 1) res = (res * a) % MOD;a = (a * a) % MOD;b >>= 1;}return res;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;// 讀取花壇權值vector<int> w(n+1);for (int i = 1; i <= n; i++) cin >> w[i];// 構建樹vector<vector<int>> adj(n+1);for (int i = 0; i < n-1; i++) {int u, v;cin >> u >> v;adj[u].push_back(v);adj[v].push_back(u);}// 計算奇數花壇總數int tot_odd = 0;for (int i = 1; i <= n; i++)tot_odd += (w[i] & 1);// 如果奇數總數為奇數，無解if (tot_odd & 1) {for (int k = 1; k <= n-1; k++)cout << "0" << (k == n-1 ? '\n' : ' ');return 0;}// 存儲子樹奇數數量vector<int> t(n+1, 0);int good = 0; // 好邊數量// DFS計算子樹信息vector<bool> vis(n+1, false);function<void(int, int)> dfs = [&](int u, int p) {int odd = w[u] & 1; // 當前節點是否為奇數for (int v : adj[u]) {if (v != p) {dfs(v, u);odd ^= t[v]; // 更新奇數計數}}t[u] = odd;// 檢查是否為好邊if (p != 0 && t[u] == 0)good++;};dfs(1, 0);// 預計算階乘和逆元vector<ll> fact(n+1, 1), inv_fact(n+1, 1);for (int i = 1; i <= n; i++)fact[i] = (fact[i-1] * i) % MOD;inv_fact[n] = pow_mod(fact[n], MOD-2); // 費馬小定理for (int i = n; i >= 1; i--)inv_fact[i-1] = (inv_fact[i] * i) % MOD;// 組合數計算函數auto comb = [&](int n, int k) -> ll {if (k < 0 || k > n) return 0;return (fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD);};// 輸出結果for (int k = 1; k <= n-1; k++) {ll res = comb(good, k);cout << res << (k == n-1 ? '\n' : ' ');}return 0;
}

• Java

import java.io.*;
import java.util.*;public class Main {static final int MOD = (int)1e9 + 7;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));// 讀取花壇數量int n = Integer.parseInt(br.readLine().trim());// 讀取每個花壇的花朵數String[] vals = br.readLine().trim().split(" ");int[] w = new int[n+1];for (int i = 1; i <= n; i++) {w[i] = Integer.parseInt(vals[i-1]);}// 構建樹List<Integer>[] adj = new ArrayList[n+1];for (int i = 0; i <= n; i++) {adj[i] = new ArrayList<>();}for (int i = 0; i < n-1; i++) {String[] edge = br.readLine().trim().split(" ");int u = Integer.parseInt(edge[0]);int v = Integer.parseInt(edge[1]);adj[u].add(v);adj[v].add(u);}// 計算奇數花壇總數int oddCount = 0;for (int i = 1; i <= n; i++) {if (w[i] % 2 == 1) {oddCount++;}}// 如果奇數總數為奇數，無解if (oddCount % 2 == 1) {StringBuilder sb = new StringBuilder();for (int k = 1; k <= n-1; k++) {sb.append("0");if (k < n-1) sb.append(" ");}System.out.println(sb.toString());return;}// 存儲子樹奇數數量和好邊數量int[] t = new int[n+1];int[] good = new int[1]; // 用數組便于在DFS中修改// DFS計算子樹信息dfs(1, 0, w, adj, t, good);// 預計算階乘和逆元long[] fact = new long[n+1];long[] invFact = new long[n+1];fact[0] = 1;for (int i = 1; i <= n; i++) {fact[i] = (fact[i-1] * i) % MOD;}invFact[n] = powMod(fact[n], MOD-2);for (int i = n; i > 0; i--) {invFact[i-1] = (invFact[i] * i) % MOD;}// 輸出結果StringBuilder result = new StringBuilder();for (int k = 1; k <= n-1; k++) {long ans = combination(good[0], k, fact, invFact);result.append(ans);if (k < n-1) result.append(" ");}System.out.println(result.toString());}// DFS計算子樹信息static void dfs(int node, int parent, int[] w, List<Integer>[] adj, int[] t, int[] good) {int isOdd = w[node] % 2; // 當前節點是否為奇數for (int child : adj[node]) {if (child != parent) {dfs(child, node, w, adj, t, good);isOdd ^= t[child]; // 更新奇數計數}}t[node] = isOdd;// 檢查是否為好邊if (parent != 0 && t[node] == 0) {good[0]++;}}// 快速冪計算static long powMod(long a, int b) {long res = 1;while (b > 0) {if ((b & 1) == 1) res = (res * a) % MOD;a = (a * a) % MOD;b >>= 1;}return res;}// 計算組合數C(n,k)static long combination(int n, int k, long[] fact, long[] invFact) {if (k < 0 || k > n) return 0;return (fact[n] * invFact[k] % MOD * invFact[n-k] % MOD);}
}

---