kmjp's blog

競技プログラミング参加記です

Codeforces #607 Div1 D. Miss Punyverse

こっちも問題文が長い…。
https://codeforces.com/contest/1280/problem/D

問題

N頂点の木を成すグラフが与えられる。
各頂点vには、2つの値B[v],W[v]が設定されている。

このグラフをいくつかの連結成分に分けたとする。
連結成分内の頂点について、sum(B)<sum(W)となる連結成分は最大何個作れるか。

解法

dp(v,win) := 頂点vのSubTree以下で、vを含まないsum(B)<sum(W)となる連結成分がwin個あるとき、vを含む連結成分のsum(W)-sum(B)

このテーブルをDFS順に葉から埋めて行けばよい。
勝ち数を減らしてもsum(W)-sum(B)を改善させる必要はないので、sum(W)>sum(B)となった時点でどん欲に連結成分を区切ってしまってよい。

int T;
int N,M;
int B[3030],W[3030];
vector<int> E[3030];

vector<pair<int,ll>> conv(vector<pair<int,ll>> A,vector<pair<int,ll>> B) {
	int a=A.size(),b=B.size();
	vector<pair<int,ll>> C(a+b,{-10000,0});
	int x,y;
	FOR(x,a) FOR(y,b) {
		C[x+y+1]=max(C[x+y+1],{A[x].first+B[y].first+(B[y].second>0),A[x].second});
		C[x+y]=max(C[x+y],{A[x].first+B[y].first,A[x].second+B[y].second});
	}
	return C;
	
}

vector<pair<int,ll>> dfs(int cur,int pre) {
	vector<pair<int,ll>> V;
	V.push_back({0,W[cur]-B[cur]});
	FORR(e,E[cur]) if(e!=pre) V=conv(V,dfs(e,cur));
	
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) cin>>B[i];
		FOR(i,N) cin>>W[i];
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		auto v=dfs(0,0);
		
		cout<<v[M-1].first+(v[M-1].second>0)<<endl;
	}
}

まとめ

Dの割には簡単?