T6 [JSOI2018] 潜入行动
很套路、很裸的一道树形 DP。看了状态就会推方程的那种。
设 \(f_{u,i,0/1,0/1}\) 表示以 \(u\) 为根的子树中有 \(i\) 个监听器、\(u\) 有没有监听器、\(u\) 有没有被监听的方案数。
显然要枚举子节点 \(v\)、\(u\) 的监听器数量 \(i\)、\(v\) 的监听器数量 \(j\)。用 \(f_{u,i}\) 和 \(f_{v,j}\) 推出 \(f_{u,i+j}\)。
然后挨个推一下就完了。
若 \(u\) 不放，也没有被监听，则 \(v\) 必定不放，但根据题意 \(v\) 之前需要被监听。故：
\[f_{u,i+j,0,0}=\sum f_{u,i,0,0}\times f_{v,j,0,1}
\]
若 \(u\) 放了，但没有被监听，则 \(v\) 必定不放，且 \(v\) 之前是否被监听无所谓。故：
\[f_{u,i+j,1,0}=\sum f_{u,i,1,0}\times(f_{v,j,0,0}+f_{v,j,0,1})
\]
若 \(u\) 不放，但被监听了，此时分两种情况：要么 \(u\) 原本就被监听了，则 \(v\) 放不放无所谓，但因为 \(u\) 没放所以 \(v\) 之前需要被监听；要么 \(u\) 原本没有被监听，则需要 \(v\) 来监听 \(u\)，也就是 \(v\) 必须放，同时因为 \(u\) 没放所以 \(v\) 之前需要被监听。故：
\[f_{u,i+j,0,1}=\sum\big(f_{u,i,0,1}\times(f_{v,j,0,1}+f_{v,j,1,1})+f_{u,i,0,0}\times f_{v,j,1,1}\big)
\]
若 \(u\) 放了，也被监听了，此时分两种情况：要么 \(u\) 原本没有被监听，则 \(v\) 必须放来监听 \(u\)，而 \(v\) 原本是否被监听无所谓；要么 \(u\) 原本就被监听了，此时 \(u\) 的所有限制都被满足，则 \(v\) 的情况也是不限的。故：
\[f_{u,i+j,1,1}=\sum\big(f_{u,i,1,0}\times(f_{v,j,1,0}+f_{v,j,1,1})+f_{u,i,1,1}\times(f_{v,j,0,0}+f_{v,j,1,0}+f_{v,j,0,1}+f_{v,j,1,1})\big)
\]
就没了。
坑点：
- 空间复杂度是 \(O(4nk)\) 的，而本题贴心地给你开了 \(\texttt{256MB}\) 的空间，所以只能开 int 数组；
- 转移方程中出现的 \(f_{u,i}\) 需要开一个临时数组存储，否则会造成后效性影响转移；
- 转移结束后再写
siz[u]+=siz[v]。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){int x=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x;
}
void write(int x,char sf='\n'){if(x<0)putchar('-'),x=~x+1;int top=0;do str[top++]=x%10,x/=10;while(x);while(top)putchar(str[--top]+48);if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=1e5+5,MOD=1e9+7;
int n,k,head[MAXN],tot;
struct{int v,to;}e[MAXN<<1];
void addedge(int u,int v){e[++tot]={v,head[u]};head[u]=tot;
}
void add(int&x,int y){x=x+y>=MOD?x+y-MOD:x+y;
}
int dp[MAXN][105][2][2],siz[MAXN],tmp[105][2][2];
void dfs(int u,int fno){siz[u]=dp[u][0][0][0]=dp[u][1][1][0]=1;for(int i=head[u],v=e[i].v;i;i=e[i].to,v=e[i].v){if(v==fno)continue;dfs(v,u);for(int i=0;i<=min(siz[u],k);++i){tmp[i][0][0]=dp[u][i][0][0],dp[u][i][0][0]=0;tmp[i][0][1]=dp[u][i][0][1],dp[u][i][0][1]=0;tmp[i][1][0]=dp[u][i][1][0],dp[u][i][1][0]=0;tmp[i][1][1]=dp[u][i][1][1],dp[u][i][1][1]=0;}for(int i=0;i<=min(siz[u],k);++i)for(int j=0;j<=min(siz[v],k-i);++j){add(dp[u][i+j][0][0],(ll)tmp[i][0][0]*dp[v][j][0][1]%MOD);add(dp[u][i+j][1][0],(ll)tmp[i][1][0]*(((ll)dp[v][j][0][0]+dp[v][j][0][1])%MOD)%MOD);add(dp[u][i+j][0][1],((ll)tmp[i][0][1]*(((ll)dp[v][j][0][1]+dp[v][j][1][1])%MOD)%MOD+(ll)tmp[i][0][0]*dp[v][j][1][1]%MOD)%MOD);add(dp[u][i+j][1][1],((ll)tmp[i][1][0]*(((ll)dp[v][j][1][0]+dp[v][j][1][1])%MOD)%MOD+(ll)tmp[i][1][1]*(((ll)dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1])%MOD)%MOD)%MOD);}siz[u]+=siz[v];}
}int main(){n=read(),k=read();for(int i=1,u,v;i<n;++i){u=read(),v=read();addedge(u,v),addedge(v,u);}dfs(1,0);write((dp[1][k][0][1]+dp[1][k][1][1])%MOD);return fw,0;
}
