題目：https://loj.ac/problem/2546

dp[ i ][ j ][ 0/1 ][ 0/1 ] 表示 i 子樹，用 j 個點，是否用 i ， i 是否被覆蓋。

注意 s1<=s0 ，別弄出負角標。

用 if 判斷一下，如果有值再轉移，會快非常多。

復雜度是 O(n*k) 的。證明：https://www.cnblogs.com/cjyyb/p/10416839.html

先約定如果一個小于 k 的子樹和一個大于 k 的子樹合并，在小于 k 的子樹那里看復雜度。

1.兩個小于 k 的子樹 cr 和 v 合并，且合并完之后還是小于 k 的；

　　對于 cr 里的每個點，要和 v 的每個點產生貢獻。雖然和很多 v 都這樣做了，但這些 v 的大小加起來小于 k （因為規定合并完還是小于 k ），所以一個點貢獻 O(k) 次。

　　如果合并完大于 k ，就在 “一個小于 k 的子樹和一個大于 k 的子樹合并” 的部分考慮復雜度了。

2.一個小于 k 的子樹 cr 和一個大于 k 的子樹 v 合并。

　　對于 cr 里的每個點，此時都要進行 O(k) 次貢獻。合并完之后 cr 的大小變成大于 k ，所以這種貢獻，每個點只會經歷一次。

3.一個大于 k 的子樹 cr 和一個大于 k 的子樹 v 合并。

　　產生 k² 的貢獻。如果是兩個大小為 k 的子樹，合并之后大小變成 2*k ；再合并進來一個大小為 k 的，大小就變成 3*k ；即這種合并最多 \( \frac{n}{k} \) 次。

綜上，復雜度是 O(n*k) 的。

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret; } int Mx(int a,int b){return a>b?a:b;} int Mn(int a,int b){return a<b?a:b;} const int N=1e5+5,M=105,mod=1e9+7; int upt(int x){while(x>=mod)x-=mod;while(x<0)x+=mod;return x;}int n,k,hd[N],xnt,to[N<<1],nxt[N<<1]; int siz[N],dp[N][M][2][2],tp[2][2]; void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;} void cz(int &x,int y){x=upt(x+y);} void dfs(int cr,int fa) {dp[cr][0][0][0]=dp[cr][1][1][0]=1; siz[cr]=1;for(int i=hd[cr],v;i;i=nxt[i])if((v=to[i])!=fa){dfs(v,cr);for(int s0=Mn(k,siz[cr]+siz[v]);s0>=0;s0--){tp[0][0]=tp[0][1]=tp[1][0]=tp[1][1]=0;for(int s1=Mx(0,s0-siz[cr]),lm=Mn(s0,Mn(siz[v],k));s1<=lm;s1++){int d=s0-s1;if(dp[cr][d][0][0]){cz(tp[0][0],(ll)dp[cr][d][0][0]*dp[v][s1][0][1]%mod);cz(tp[0][1],(ll)dp[cr][d][0][0]*dp[v][s1][1][1]%mod);}if(dp[cr][d][0][1])cz(tp[0][1],(ll)dp[cr][d][0][1]*(dp[v][s1][0][1]+dp[v][s1][1][1])%mod);if(dp[cr][d][1][0]){cz(tp[1][0],(ll)dp[cr][d][1][0]*(dp[v][s1][0][0]+dp[v][s1][0][1])%mod);cz(tp[1][1],(ll)dp[cr][d][1][0]*(dp[v][s1][1][0]+dp[v][s1][1][1])%mod);}if(dp[cr][d][1][1]){cz(tp[1][1],(ll)dp[cr][d][1][1]*((ll)dp[v][s1][0][0]+dp[v][s1][0][1]+dp[v][s1][1][0]+dp[v][s1][1][1])%mod);}}for(int f0=0;f0<=1;f0++)for(int f1=0;f1<=1;f1++)dp[cr][s0][f0][f1]=tp[f0][f1];}siz[cr]+=siz[v];} } int main() {n=rdn();k=rdn();for(int i=1,u,v;i<n;i++)u=rdn(),v=rdn(),add(u,v),add(v,u);dfs(1,0);printf("%d\n",upt(dp[1][k][0][1]+dp[1][k][1][1]));return 0; }

?

轉載于:https://www.cnblogs.com/Narh/p/10749068.html

總結

以上是生活随笔為你收集整理的LOJ 2546 「JSOI2018」潜入行动——树形DP的全部內容，希望文章能夠幫你解決所遇到的問題。

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