自动搬运

查看原文

来自洛谷，原作者为

	yijan 我结束了！

搬运于2025-08-24 22:21:10，当前版本为作者最后更新于2020-04-25 12:27:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

由于 Latex 挂了，建议到 Luogu 博客或者 这里 查看。

我们记 “恰好有 $k$ 次非平局” 的方案数是 $g(k)$ ，“钦定有 $k$ 次非平局” 的方案数是 $f(k)$ 。发现这是一个二项式反演的形式，由二项式反演有公式：（不会可以百度）

$$f(n)=\sum\limits_{i=n}^m{i\choose n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}^m(-1)^{i-n}{i\choose n}f(i) $$

所以我们只要求出 $f(k)$ 就做完了这个题。我们可以 dp 求出 $f$ ，设 $dp[u][x]$ 表示 $u$ 子树内钦定选择了 $x$ 对点，这 $x$ 对点均呈 祖先 - 子孙 的关系（也就是这 $x$ 局钦定会比出胜负）。于是发现这东西可以直接树形背包算。

转移就是正常的树形背包，最后还需要考虑钦定这个点和某个后代的情况，这种情况的转移就是从子树内未被钦定的点中选择一个点。

然后我交上去的代码多输出了个 $0$ 考试的时候没看到 /kk

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 5006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define P 998244353
int n;
int A[MAXN];

int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , ecn;
void ade( int u , int v ) {
    to[++ ecn] = v , nex[ecn] = head[u] , head[u] = ecn;
}

int dp[MAXN][MAXN] , siz[MAXN] , sz[MAXN];
int pd[MAXN];
void dfs( int u , int fa ) {
    siz[u] = 1 , sz[u] = A[u];
    dp[u][0] = 1;
    for( int i = head[u] , v ; i ; i = nex[i] ) {
        v = to[i];
        if( v == fa ) continue;
        dfs( v , u );
        rep( k , 0 , siz[u] + siz[v] ) pd[k] = 0;
        rep( j , 0 , min( siz[u] , n / 2 ) ) if( dp[u][j] )
            rep( k , 0 , min( siz[v] , n / 2 - j ) ) if( dp[v][k] )
                pd[j + k] = ( pd[j + k] + dp[u][j] * 1ll * dp[v][k] % P ) % P;
        rep( k , 0 , siz[u] + siz[v] ) dp[u][k] = pd[k];
        siz[u] += siz[v] , sz[u] += sz[v];
    }
    per( i , min( sz[u] , siz[u] - sz[u] ) , 1 ) dp[u][i] = ( dp[u][i] + dp[u][i - 1] * 1ll * ( ( A[u] ? ( siz[u] - sz[u] ) : ( sz[u] ) ) - ( i - 1 ) ) % P ) % P;
}

int J[MAXN] , iJ[MAXN];
int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = 1ll * ret * x % P;
        x = 1ll * x * x % P , a >>= 1;
    }
    return ret;
}
int C( int a , int b ) {
    return J[a] * 1ll * iJ[b] % P * iJ[a - b] % P;
}

void solve() {
    cin >> n;
    J[0] = iJ[0] = 1;
    rep( i , 1 , MAXN - 1 ) J[i] = J[i - 1] * 1ll * i % P , iJ[i] = Pow( J[i] , P - 2 );
    rep( i , 1 , n )
        scanf("%1d",A + i);
    int u , v;
    rep( i , 2 , n ) scanf("%d%d",&u,&v) , ade( u , v ) , ade( v , u );
    dfs( 1 , 1 );
    int re = 0;
    rep( i , 0 , n / 2 + 1 ) dp[1][i] = dp[1][i] * 1ll * J[n / 2 - i] % P;
    rep( i , 0 , n / 2 ) {
        re = 0;
        rep( j , i , n / 2 )
            re += C( j , i ) * 1ll * ( ( j - i & 1 ) ? P - 1 : 1 ) % P * dp[1][j] % P , re %= P;
        printf("%d ",re);
    }
}

signed main() {
//    freopen("match.in","r",stdin);
//    freopen("match.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}