CPSCO2019 Session2 : E - Mogu Mogu Gummi

手がベタベタしそう。
https://atcoder.jp/contests/cpsco2019-s2/tasks/cpsco2019_s2_e

問題

根付き木を成す無向グラフが与えられる。
各辺には耐久度H[i]が設定されている。

点を指定すると、根とその点のパス上にある辺の耐久度を1減らすことができ、途中耐久度が0になった辺が生じるとその辺は消滅する。
なお、途中辺が消滅しているような点は選択できない。

最適な選択順を行う場合、連結成分は最大何個にできるか。

解法

連結成分は(消滅辺数+1)なので、消滅する辺を最大化しよう。
根から遠いところの辺を消滅させるには、そこまでに至るパス上の辺がそれ以上の耐久度が無ければならない。

そこで以下を考える。
dp(v,n) := 点vのsubtree(vの親からvに至る辺含む)において、n箇所辺を消滅させる場合の親方向に必要な耐久度の最大値

dp(v,n)は葉から順に更新でき、おわゆるO(N^2)系の更新が可能な木DPとなる。
もしdp(v,n)がvから親方向の耐久度以下の場合、dp(v,n+1) := 親方向の辺の耐久度　とできる。

int N;
int P[5050];
ll H[5050];
int C[5050];
ll dp[5050][5050];
vector<int> E[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(x,N+1) FOR(y,N+1) dp[x][y]=1LL<<60;
	FOR(i,N-1) {
		cin>>P[i+1]>>H[i+1];
		E[P[i+1]].push_back(i+1);
	}
	
	for(i=N-1;i>=0;i--) {
		dp[i][0]=0;
		FORR(e,E[i]) {
			for(x=C[i];x>=0;x--) {
				for(y=C[e];y>=0;y--) {
					dp[i][x+y]=min(dp[i][x+y],dp[i][x]+dp[e][y]);
				}
			}
			C[i]+=C[e];
		}
		if(i) {
			for(x=C[i];x>=0;x--) {
				if(dp[i][x]<=H[i]) dp[i][x+1]=min(dp[i][x+1],H[i]);
				else dp[i][x]=1LL<<60;
			}
		}
		C[i]++;
	}
	
	for(x=N;x>=0;x--) {
		if(dp[0][x]<1LL<<60) {
			cout<<x+1<<endl;
			break;
		}
	}
	
	
	
}

まとめ

最近この種のO(N^2)系木DPの計算量で迷わなくなってきた。