Codeforces #603 Div2 F. Economic Difficulties

問題設定が若干ややこしいかも。
http://codeforces.com/contest/1263/problem/F

問題

以下のような平面グラフを考える。
Y軸上に、横1列にN個の頂点があるとする。
Y座標の正の部分には、根付き木がある。辺はY座標の大きい方から小さい方に流れ、かつ葉は上記N個の頂点である。
同様に、Y座標の負の部分にも根付き木がある。辺はY座標の小さい方から大きい方に流れ、かつ葉は上記N個の頂点である。

N個の頂点いずれも、Y座標の正の部分か負の部分いずれかの根から到達できるようにした中で、できるだけ辺を減らしたい。
減らせる辺は最大何本か。

解法

f(a,b) := c=max(a,b)までのprefixのうち、最後に上の根から到達可能な頂点はaで、下の根から到達可能な頂点はbであるような状態における必要辺数
とする。次、c+1番目の頂点は上と下それぞれから遷移する場合を考え、f(c,b)とf(a,c)を更新していこう。
辺の数 - min(f(N,*),f(*,N))が解。

int N;
int M[2];
int P[2][2010];
vector<int> E[2][2010];
int R[2][2010];
int D[2][2010];

int dif[2][2010][2010];
int dp[2010][2010];

void dfs(int id,int cur,int d) {
	D[id][cur]=d;
	FORR(e,E[id][cur]) dfs(id,e,d+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(x,2) {
		cin>>M[x];
		FOR(i,M[x]-1) {
			cin>>P[x][i+2];
			E[x][P[x][i+2]].push_back(i+2);
		}
		dfs(x,1,0);
		FOR(i,N) {
			cin>>R[x][i];
		}
		
		FOR(i,N) {
			dif[x][0][i+1]=D[x][R[x][i]];
		}
		FOR(j,N) FOR(i,j) {
			int a=R[x][i];
			int b=R[x][j];
			while(D[x][a]>D[x][b]) a=P[x][a];
			while(D[x][a]<D[x][b]) b=P[x][b];
			while(a!=b) {
				a=P[x][a];
				b=P[x][b];
			}
			dif[x][i+1][j+1]=D[x][R[x][j]]-D[x][b];
		}
	}
	FOR(x,N+1) FOR(y,N+1) dp[x][y]=101010;
	dp[0][1]=dif[1][0][1];
	dp[1][0]=dif[0][0][1];
	int mi=1<<20;
	if(N==1) mi=min(dp[0][1],dp[1][0]);
	FOR(x,N+1) FOR(y,N+1) if(x!=y) {
		int nex=max(x,y)+1;
		dp[x][nex]=min(dp[x][nex],dp[x][y]+dif[1][y][nex]);
		dp[nex][y]=min(dp[nex][y],dp[x][y]+dif[0][x][nex]);
		if(nex==N) mi=min({mi,dp[x][nex],dp[nex][y]});
	}
	cout<<(M[0]+M[1]-2)-mi<<endl;
}

まとめ

Div2の3000ptとしては簡単。