Livearchive 5741 Wealthy Family

問題

根付き木が与えられる。
それぞれの頂点には重みがついている。

今、この木からちょうどk個の頂点{a1, a2, ..., ak}を選ぶ。
ここで、i != jなる任意の1≦i, j≦kについて、aiがajの先祖であってはならない。

このとき、選んだ頂点の重みの和の最大値を求めよ。

制約条件

木の頂点数≦150000
重みは1以上1000以下の整数

方針

動的計画法による。

dp[i][j]を、i番目の頂点以下で、j個の頂点を選んだときの重みの和の最大値、
とするような動的計画法だと、O(nk^2)かかってTLEで、上手くやる必要がある。

以下のようにする。

木の根から再帰する。
rec(int cur, int *dp)で、dp[i]を、今まで見た頂点のうち、
curと干渉しない頂点だけをi個使って作れる重みの和の最大値が渡されているとする。

recの中で、dpを書き換えて、
自分以下の頂点も使ったときの、i個使ったときに作れる重みの和の最大値とする。

書き換えは、まずdp2[i]を、自分の子以下も使って、作れる重みの最大の和の配列とする。
dp2はdp[]をコピーして初期化し、recに全ての子について、dp2を渡してやればよい。

その後、dp[i]をmax(dp2[i], dp[i - 1] + w[cur])として書き換える。

ソースコード

int n, m, w[150000];
int dp_[150000][301];
vector<vi> e;

void rec(int c, int *dp){
	int *dp2 = dp_[c];
	rep(i, m + 1) dp2[i] = dp[i];
	
	rep(i, e[c].size()) rec(e[c][i], dp2);
	for(int i = m; i >= 0; i--){
		dp[i] = dp2[i];
		if(i > 0 && dp[i - 1] >= 0) dp[i] = max(dp[i], dp[i - 1] + w[c]);
	}
}

int main()
{
	while(cin >> n >> m){
		e.clear(); e.resize(n);
		
		int root;
		
		rep(i, n){
			int p;
			cin >> p >> w[i];
			if(--p < 0) root = i;
			else e[p].pb(i);
		}
		
		int ans[301];
		rep(i, m + 1) ans[i] = -1;
		ans[0] = 0;
		
		rec(root, ans);
		
		if(ans[m] < 0) cout << "impossible" << endl;
		else cout << ans[m] << endl;
	}
	return 0;
}