C. Helga Hufflepuff’s Cup

比較經(jīng)典的樹形dp套路。由于題目限制某類點的數(shù)量，因而狀態(tài)需要記錄一下子樹中該特殊點的數(shù)量。

設計dp：
$f_{u,j,k}$以$u$為根的子樹中，選了$j$個特殊值（點權(quán)==K），$u$的權(quán)值是0/1/2(分別表示小于K/等于K/大于K)

轉(zhuǎn)移用一個數(shù)組輔助轉(zhuǎn)移即可

時間復雜度$O(NK)$

LLC的博客

#include<bits/stdc++.h>using namespace std; using ll=long long;constexpr int N=100005,mod=1e9+7; int h[N],e[2*N],ne[2*N],idx; void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;} int n,m,K,X; ll f[N][11][3];// f[u][j][k] 以u為根 選了j個特殊的點 u狀態(tài)是0/1/2 小于K/等于K/大于K ll g[11][3]; int sz[N]; void dfs(int u,int fa) {f[u][0][0]=K-1;f[u][1][1]=1;f[u][0][2]=m-K;sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa) continue;dfs(v,u);memset(g,0,sizeof g);for(int j=0;j<=min(X,sz[u]);j++)for(int k=0;k<=sz[v]&&j+k<=X;k++){g[j+k][0]=(g[j+k][0]+f[u][j][0]*(f[v][k][0]+f[v][k][1]+f[v][k][2]))%mod;g[j+k][1]=(g[j+k][1]+f[u][j][1]*f[v][k][0])%mod;g[j+k][2]=(g[j+k][2]+f[u][j][2]*(f[v][k][0]+f[v][k][2]))%mod;}sz[u]+=sz[v];for(int j=0;j<=min(X,sz[u]);j++)for(int k=0;k<3;k++) f[u][j][k]=g[j][k];} } int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;memset(h,-1,sizeof h);for(int i=1;i<n;i++){int u,v;cin>>u>>v;add(u,v),add(v,u);}cin>>K>>X;dfs(1,0);ll ans=0;for(int i=0;i<=X;i++)for(int j=0;j<3;j++)ans=(ans+f[1][i][j])%mod;cout<<ans<<'\n';return 0; }

總結(jié)

以上是生活随笔為你收集整理的codeforces855 C. Helga Hufflepuff‘s Cup（树形dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。