题解

题目描述

小红有一棵树，共有 $n$ 个节点，每个节点 $i$ 上有一个整数权值 $W_i$。她希望通过删除若干条边，将这棵树分割为若干个连通块，使得每个连通块中所有节点的权值之和都是偶数。

请你求出，对每个 $k\ (1 \le k \le n-1)$，删除 $k$ 条边后得到的 $k+1$ 个连通块满足条件的方案数。若不存在满足条件的方案，对应的答案记为 $0$。

注意：两种删除边的方案若删除的边集合不同，则视为不同的方案。结果对 $10^9+7$ 取模。

思路概述

1. 问题本质：每个连通块的节点权值和要为偶数。整个树节点权值之和若为奇数，则无解。否则，拆分的连通块数越多，需要更多边满足构成偶数和子树。
2. 子树和与可切边：对树做一次DFS，计算以任意根（如 1 号节点）为根时，每个节点为根的子树权值和 $S_u$。如果 $S_u$ 为偶数，则可考虑切断其与父节点的边，使得该子树与其余部分各自的和均为偶数。
3. 可切边的数量：设可切边总数为 $m$。这些边独立性较强：删除任意子集都不会破坏其他子树的偶数和性质。事实上，只需保证所选切断的边都在这些可切边集合中。
4. 组合计数：从 $m$ 条可切边中恰好选 $k$ 条删除，方案数为 $C(m, k)$，其中 $k \le m$。若 $k > m$，答案为 $0$。
5. 前置判断：若整棵树总权值和 $T$ 为奇数，则对所有 $k$ 输出 0。
6. 复杂度：DFS 计算子树和 $O(n)$，统计 $m$。预处理阶乘与逆元至 $n$，支持快速组合查询，每次 $O(1)$。整体 $O(n)$。

题解详解

1. 子树和计算

• 选择节点 $1$ 作为根，执行 DFS。
• 对每个节点 $u$，累加自身权值 $W_u$ 与所有子节点的子树和，得到 $S_u$。
• 若 $u\neq 1$ 且 $S_u$ 为偶数，则边 $(u, \mathrm{fa}[u])$ 为可切边。

2. 可切边计数

• 在 DFS 过程中统计可切边数 $m$。
• 整树总权值和 $T = S_1$。若 $T$ 为奇数，则 $m$ 暂不统计，直接对所有 $k$ 输出 0。

3. 组合数预处理

• 预先计算 $\mathrm{fact}[i]=i!\bmod P$ 和 $\mathrm{inv}[i]=(i!)^{-1}\bmod P$，$i=0\ldots n$。

• 组合数公式：

  

4. 输出答案

• 对 $k=1$ 到 $n-1$：若 $k\le m$ 输出 $C(m,k)$，否则输出 $0$。

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100000;
const int MOD = 1000000007;

int n;
vector<int> g[MAXN+1];
ll W[MAXN+1], subsum[MAXN+1];
int m = 0; // 可切边数量

// 快速幂取模
ll modexp(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll fact[MAXN+1], invfact[MAXN+1];

// 预处理阶乘和逆元
void init_fact(int N) {
    fact[0] = 1;
    for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % MOD;
    invfact[N] = modexp(fact[N], MOD-2);
    for (int i = N; i > 0; --i) invfact[i-1] = invfact[i] * i % MOD;
}

// 计算组合数 C(n,k)
ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
}

// DFS 计算子树和并统计可切边
void dfs(int u, int fa) {
    subsum[u] = W[u];
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        subsum[u] += subsum[v];
    }
    // 根节点无父边
    if (fa != 0 && subsum[u] % 2 == 0) {
        ++m;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> W[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    dfs(1, 0);
    // 整树和
    ll total = subsum[1];
    if (total % 2 != 0) {
        // 无解
        for (int k = 1; k < n; ++k) cout << 0 << (k+1<n? ' ' : '\n');
        return 0;
    }

    init_fact(n);
    // 输出 C(m, k)
    for (int k = 1; k < n; ++k) {
        cout << C(m, k) << (k+1<n? ' ' : '\n');
    }
    return 0;
}

Python

import sys
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7

# 读取输入
n = int(sys.stdin.readline())
W = [0] + list(map(int, sys.stdin.readline().split()))
g = [[] for _ in range(n+1)]
for _ in range(n-1):
    u, v = map(int, sys.stdin.readline().split())
    g[u].append(v)
    g[v].append(u)

subsum = [0]*(n+1)
m = 0

def dfs(u, fa):
    global m
    subsum[u] = W[u]
    for v in g[u]:
        if v == fa: continue
        dfs(v, u)
        subsum[u] += subsum[v]
    if fa != 0 and subsum[u] % 2 == 0:
        m += 1

# 执行DFS
dfs(1, 0)

# 整树总和
if subsum[1] % 2 == 1:
    print(" ".join(['0']*(n-1)))
    sys.exit(0)

# 预处理阶乘与逆元
fact = [1]*(n+1)
invfact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = fact[i-1] * i % MOD
invfact[n] = pow(fact[n], MOD-2, MOD)
for i in range(n, 0, -1):
    invfact[i-1] = invfact[i] * i % MOD

# 组合数函数
from math import comb

def C(a, b):
    if b < 0 or b > a:
        return 0
    return fact[a] * invfact[b] % MOD * invfact[a-b] % MOD

# 输出结果
res = [str(C(m, k)) for k in range(1, n)]
print(" ".join(res))

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    static int n;
    static long[] W, subsum;
    static List<Integer>[] g;
    static int m = 0; // 可切边计数

    // 快速幂
    static long modexp(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    // 阶乘和逆元
    static long[] fact, invfact;
    static void initFact(int N) {
        fact = new long[N+1];
        invfact = new long[N+1];
        fact[0] = 1;
        for (int i = 1; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
        invfact[N] = modexp(fact[N], MOD-2);
        for (int i = N; i >= 1; i--) invfact[i-1] = invfact[i] * i % MOD;
    }

    // 组合数 C(n,k)
    static long C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
    }

    // DFS 计算子树和并统计
    static void dfs(int u, int fa) {
        subsum[u] = W[u];
        for (int v : g[u]) {
            if (v == fa) continue;
            dfs(v, u);
            subsum[u] += subsum[v];
        }
        if (fa != 0 && subsum[u] % 2 == 0) m++;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        W = new long[n+1]; subsum = new long[n+1];
        g = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        String[] parts;
        parts = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) W[i] = Long.parseLong(parts[i-1]);
        for (int i = 1; i < n; i++) {
            parts = br.readLine().split(" ");
            int u = Integer.parseInt(parts[0]);
            int v = Integer.parseInt(parts[1]);
            g[u].add(v);
            g[v].add(u);
        }
        dfs(1, 0);
        if (subsum[1] % 2 == 1) {
            // 无解
            for (int k = 1; k < n; k++) {
                System.out.print(0);
                if (k+1 < n) System.out.print(" ");
            }
            return;
        }
        initFact(n);
        for (int k = 1; k < n; k++) {
            System.out.print(C(m, k));
            if (k+1 < n) System.out.print(" ");
        }
    }
}

题目内容

小红有一棵树，每个节点上都有一个整数权值。她希望通过删除若干条边，将这棵树分割

为若干个连通块，使得每个连通块中所有节点的权值之和都是偶数。

请你求出，对于每个$k(1 ≦k≦n-1)$，删除k条边后得到的$k+1$个连通块满足条件的方案数。如果不存在满足条件的方案，对应的答案记为$0$。

注意:两种删除边的方案若删除的边集合不同，则视为不同的方案。

输入描述

第一行给出一个整数$n$，表示树的节点数。

第二行给出$n$个整数$W_1,W_2,...,W_n$，其中$W_i$表示节点$i$的权值。

接下来$n-1$行，每行包含两个整数$u$与$v(1≦u,v≦n,u≠v)$，表示节点$u$与节点$v$ 之间有一条边，保证给定的图构成一棵树。

$2≦n≦10^5$

$1≦w_i≦10^9$

$1≦u,v≦n$

输出描述

输出$n-1$个数，第$i$个数表示删除$i$条边后满足条件的方案数。由于答案可能非常大，请对答案取模$10^9+7$后输出。

样例1

输入

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

输出

3 3 1 0

说明

当$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$种。