[ABC207F] Tree Patrolling
弱智 DP 题，设 \(f(i,j,0/1/2)\) 表示在点 \(i\)，子树中有 \(j\) 个点被覆盖，且 \(i\) 点自身状态是未被覆盖/被自身覆盖/被某个儿子覆盖，然后树上背包更新就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=2e3+100;
int n,x,y;
int f[N][N][3],g[N][3],sz[N];
vector<int> v[N];
void dfs(int x,int fa){
f[x][0][0]=1;
f[x][1][1]=1;
sz[x]=1;
for(auto y:v[x])if(y!=fa){
dfs(y,x);
for(int i=0;i<=sz[x];i++){
for(int j=0;j<=sz[y];j++){
(g[i+j][0]+=f[x][i][0]*f[y][j][0]%mod)%=mod;
(g[i+j+1][2]+=f[x][i][0]*f[y][j][1]%mod)%=mod;
(g[i+j][0]+=f[x][i][0]*f[y][j][2]%mod)%=mod;
(g[i+j+1][1]+=f[x][i][1]*f[y][j][0]%mod)%=mod;
(g[i+j][1]+=f[x][i][1]*f[y][j][1]%mod)%=mod;
(g[i+j][1]+=f[x][i][1]*f[y][j][2]%mod)%=mod;
(g[i+j][2]+=f[x][i][2]*f[y][j][0]%mod)%=mod;
(g[i+j][2]+=f[x][i][2]*f[y][j][1]%mod)%=mod;
(g[i+j][2]+=f[x][i][2]*f[y][j][2]%mod)%=mod;
}
}
sz[x]+=sz[y];
for(int i=0;i<=sz[x];i++){
for(int j=0;j<3;j++){
f[x][i][j]=g[i][j];
g[i][j]=0;
}
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
for(int i=0;i<=n;i++){
int res=0;
for(int j=0;j<3;j++) (res+=f[1][i][j])%=mod;
cout<<res<<'\n';
}
return 0;
}