[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;
}