AtCoder ABC #207 : F - Tree Patrolling

ペナルティ込みだと、B,C,D,Eより短い時間で解いている…。
https://atcoder.jp/contests/abc207/tasks/abc207_f

問題

N頂点の木を成すグラフが与えられる。
このうちいくつかの頂点に、高橋君を配置するとする。
高橋君は、自身のいる頂点及びその隣接頂点を警備する。

警備された頂点数がK個であるような高橋君の配置は何通りか。
K=0～Nについて求めよ。

解法

O(N^3)に見えてO(N^2)で解けるタイプの木DP問題。
頂点v毎に、以下の状態毎に組み合わせの数を数えよう。

• vのSubtree内のうち警備された頂点数
• vの状態が、以下のいずれか
  • 警備されていない
  • 高橋君がいて警備されている
  • 高橋君がいないが、その隣接頂点の高橋君によって警備されている

int N;
vector<int> E[2020];
int C[2020];
const ll mo=1000000007;

ll dp[2020][2020][3]; // 0-not 1-covered 2-placed

void dfs(int cur,int pre) {
	ll from[2020][3]={};
	C[cur]=1;
	from[0][0]=1;
	from[1][2]=1;
	FORR(e,E[cur]) if(e!=pre) {
		ll to[2020][3]={};
		dfs(e,cur);
		int x,y;
		FOR(x,C[cur]+1) FOR(y,C[e]+1) {
			(to[x+y+1][2]+=from[x][2]*dp[e][y][0])%=mo;
			(to[x+y][2]+=from[x][2]*(dp[e][y][1]+dp[e][y][2]))%=mo;
			(to[x+y][1]+=from[x][1]*(dp[e][y][0]+dp[e][y][1]+dp[e][y][2]))%=mo;
			(to[x+y][0]+=from[x][0]*(dp[e][y][0]+dp[e][y][1]))%=mo;
			(to[x+y+1][1]+=from[x][0]*(dp[e][y][2]))%=mo;
		}
		C[cur]+=C[e];
		
		
		
		swap(from,to);
	}
	
	int x,y;
	FOR(x,2001) FOR(y,3) dp[cur][x][y]=from[x][y];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0);
	FOR(i,N+1) {
		ll ret=dp[0][i][0]+dp[0][i][1]+dp[0][i][2];
		cout<<ret%mo<<endl;
	}
	
	
}

まとめ

なんかB,C,D,Eで苦戦してるんだよな。