牛客 - Rebuild Tree

传送门：牛客 - Rebuild Tree

思路分析

删掉$\text{k}$条边之后，形成了$\text{k+1}$个连通块。

连边相当于生成$\text{k+1}$个点的树，我们通过$\text{purfer}$序列进行推导

令 $m = k+1$，$s_i$为连通块大小，$d_i$为度数，$p_i$为在$\text{purfer}$序列中的出现次数（由$\text{purfer}$序列易得$d_i = p_i+1$）

$\begin{aligned}
ans &=\sum_{Tree}\prod\limits_{i=1}^{m}s_{i}^{d_{i}}\\
&=\sum_{Tree}\prod\limits_{i=1}^{m}s_{i}^{p_{i}+1}\\
&=\sum_{Tree}\prod\limits_{i=1}^{m}s_{i}^{p_i}\prod\limits_{i=1}^{m}s_{i}\\
&=(\sum\limits_{i=1}^{m}s_i)^{m-2}\prod\limits_{i=1}^{m}s_{i}\\
&=n^{m-2}\prod\limits_{i=1}^{m}s_{i}\\
\end{aligned}$

$\prod\limits_{i=1}^{m}s_{i}$比较难算，考虑转化为一个等价问题：删除$\text{k}$条边，每个连通块里恰好选一个点的方案数。可以用树形$\text{dp}$来解决，$dp_{i,j,0/1}$表示$\text{i}$这棵子树删了$\text{j}$条边，$\text{i}$所在的连通块有没有选点。

以$\text{1}$为根，最后的答案就是$n^{m-2}\times dp_{1,k,1}$

AC代码

#include <bits/stdc++.h>
#define V vector
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sz(x) (int)(x).size()
#define each(x,a) for(auto& x:a)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define mcp(a,b) memcpy(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int mod = 998244353;
const int N = 5e4+10;

int dp[N][111][2],tmp[111][2],siz[N],n,k;
V<int>e[N];

void dfs(int u,int f){
    siz[u] = 1;
    dp[u][0][0] = dp[u][0][1] = 1;
    each(v,e[u]){
        if(v == f) continue;
        dfs(v,u);
        mem(tmp,0);
        for(int i=0;i<=min(siz[u],k);i++){
            for(int j=0;j<=min(siz[v],k);j++){
                if(i+j>k) break;
                tmp[i+j][0] = (tmp[i+j][0] + dp[u][i][0] * dp[v][j][0] % mod )%mod;
                tmp[i+j][1] = (tmp[i+j][1] + dp[u][i][0] * dp[v][j][1] % mod )%mod;
                tmp[i+j][1] = (tmp[i+j][1] + dp[u][i][1] * dp[v][j][0] % mod )%mod;
                if(i+j+1>k) break;
                tmp[i+j+1][0] = (tmp[i+j+1][0] + dp[u][i][0] * dp[v][j][1] % mod )%mod;
                tmp[i+j+1][1] = (tmp[i+j+1][1] + dp[u][i][1] * dp[v][j][1] % mod )%mod;
            }
        }
        siz[u]+=siz[v];
        mcp(dp[u],tmp);
    }
}



signed main() {

#ifdef xiaofan
    clock_t stTime = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
/*==========================begin============================*/
    IOS;
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].pb(v);
        e[v].pb(u);
    }
    dfs(1,1);
    int ans = dp[1][k][1];
    for(int i=1;i<=k-1;i++) ans = (ans*n)%mod;
    cout<<ans<<endl;



/*===========================end=============================*/
#ifdef xiaofan
    cerr << "Time Used:" << clock() - stTime << "ms" <<endl;
#endif
    return 0;
}