AISing Programming Contest 2019 : E - Attack to a Tree

O(N^2)の木DPだろうと思いつつ状態を定めるのに手間取った。
https://atcoder.jp/contests/aising2019/tasks/aising2019_e

問題

N頂点の木を成す無向グラフが与えられる。
各頂点iには、０ではない整数値A[i]が設定されている。
いくつかの辺を切断し、各連結成分が下記いずれかを満たすようにするには、最少で何本辺を切断すればよいか。

• 連結成分内の全頂点の整数値が正である。
• 連結成分内の全頂点の整数の総和が負である。

解法

連結成分内に１個でも負の値があるなら、その連結成分の総和は小さくなるようにしておいた方がよい。
よって以下を考える。
f(v,n) := vのsubtree以下でn個辺を切断して条件を満たすようにしたときで、vを含む連結成分中の頂点の整数値がすべて正であるような状態が存在するなら、その総和の最小値。
g(v,n) := vのsubtree以下でn個辺を切断して条件を満たすようにしたときで、vを含む連結成分中の頂点の整数値に1個でも負であるような状態が存在するなら、その総和の最小値。

各頂点vに対し、子頂点f(c,n),g(c,n)が定まっているとき、f(c,n)が存在している場合や、g(c,n)が負の場合v-c間は切断してもよいししなくてもよい。
そうでない場合は切断できない、としてf(v,*),g(v,*)を求めていく。

f(root,n)が存在する、またはg(root,n)が負であるような最小のnが解。

int N;
int A[5050];
vector<int> E[5050];
ll dp[5060][5060][2];
int C[5050];
ll to[5053][2];

void dfs(int cur,int pre) {
	C[cur]=1;
	
	dp[cur][0][A[cur]>0]=A[cur];
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		
		int x,y;
		FOR(x,5050) to[x][0]=to[x][1]=1LL<<60;
		for(x=0;x<=C[cur]-1;x++) {
			for(y=0;y<=C[e]-1;y++) {
				
				if(dp[e][y][0]<0 || dp[e][y][1]<1LL<<60) {
					to[x+y+1][0]=min(to[x+y+1][0],dp[cur][x][0]);
					to[x+y+1][1]=min(to[x+y+1][1],dp[cur][x][1]);
				}
				to[x+y][1]=min(to[x+y][1],dp[cur][x][1]+dp[e][y][1]);
				to[x+y][0]=min(to[x+y][0],dp[cur][x][0]+dp[e][y][1]);
				to[x+y][0]=min(to[x+y][0],dp[cur][x][1]+dp[e][y][0]);
				to[x+y][0]=min(to[x+y][0],dp[cur][x][0]+dp[e][y][0]);
			}
		}
		FOR(x,5050) {
			dp[cur][x][0]=to[x][0];
			dp[cur][x][1]=to[x][1];
		}
		C[cur]+=C[e];
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(x,5050) FOR(y,5050) dp[x][y][0]=dp[x][y][1]=1LL<<60;
	
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,-1);
	for(i=0;i<=5050;i++) {
		if(dp[0][i][0]<0) return _P("%d\n",i);
		if(dp[0][i][1]<1LL<<60) return _P("%d\n",i);
	}
	
	
}

まとめ

巨大なローカル変数でREしてた…。