題目鏈接：點擊查看

題目大意：給出一棵 $n$ 個節點的樹，現在可以刪掉 $k$ 條邊，然后加上 $k$ 條邊，問有多少種方案使得操作后 $n$ 個點仍然是一棵樹

題目分析：原樹刪掉 $k$ 條邊后會變成一個具有 $k+1$ 個連通塊的森林，設每個連通塊的大小依次為 $s[1]...s[k+1]$，考慮 prufer 序列，答案就是 $n^{k?1}\prod _{i=1}^{k}s[i]$。可以這樣理解，如果想要將 $k+1$ 個連通塊繼續加邊直到變成一棵樹，那么需要構造一個長度為 $k?1$ 的 prufer 序列，每個位置可以取值 $[1,n]$，這樣就將最終樹的形態確定下來了，我們還需要確定刪除的是哪 $k$ 條邊，這個可以用每個連通塊大小的乘積表示所有情況。

現在問題轉換為如何求解 $\prod _{i=1}^{k}s[i]$，考慮轉換為等價問題：刪掉 $k$ 條邊，并且每個連通塊內恰好選了一個點的方案數。$dp[i][j][0/1]$ 代表對于子樹 $i$，刪了 $j$ 條邊，點 $i$ 所在的連通塊是否已經選擇了點的方案數，然后就是樹形 dp 了，枚舉每條邊選擇是否刪除進行轉移

代碼：

// Problem: Rebuild Tree // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11255/D // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=5e4+100; const int mod=998244353; int n,k,sz[N]; vector<int>node[N]; LL dp[N][110][2],tmp[110][2]; void dfs(int u,int fa) {sz[u]=1;dp[u][0][0]=dp[u][0][1]=1;//一條邊不刪只有一種情況for(auto v:node[u]) {if(v==fa) {continue;}dfs(v,u);memset(tmp,0,sizeof(tmp));for(int i=0;i<sz[u]&&i<=k;i++) {//u當前子樹中刪了多少條邊for(int j=0;j<sz[v]&&i+j<=k;j++) {//v子樹中刪了多少條邊//not deletetmp[i+j][0]=(tmp[i+j][0]+dp[u][i][0]*dp[v][j][0])%mod;tmp[i+j][1]=(tmp[i+j][1]+dp[u][i][0]*dp[v][j][1]+dp[u][i][1]*dp[v][j][0])%mod;if(i+j==k) {continue;}//delete (u,v)//因為v的子樹是獨立的，所以刪掉(u,v)后，v的子樹中必須已經選擇了點才行tmp[i+j+1][0]=(tmp[i+j+1][0]+dp[u][i][0]*dp[v][j][1])%mod;tmp[i+j+1][1]=(tmp[i+j+1][1]+dp[u][i][1]*dp[v][j][1])%mod;}}memcpy(dp[u],tmp,sizeof(tmp));sz[u]+=sz[v];} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n),read(k);for(int i=1;i<n;i++) {int u,v;read(u),read(v);node[u].push_back(v);node[v].push_back(u);}dfs(1,-1);LL ans=dp[1][k][1];for(int i=1;i<k;i++) {ans=(ans*n)%mod;}cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的2021牛客多校4 - Rebuild Tree(树形dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。