Codeforces #831 : E. Hanging Hearts

ダメダメだったこの回だけど、この問題は割とすんなりだな。
https://codeforces.com/contest/1740/problem/E

問題

N頂点の根付き木が与えられる。
各点には、1～Nの番号を1点ずつ任意に振ったとする。

以下の手順をN回繰り返し、数列Sを構築する。

• 葉を1個選び、その振られた番号をSの末尾に加える。
• 選んだ葉が根でない場合、親頂点の番号が選んだ葉の番号で代入する。
• 選んだ葉を取り除く。

SのLISの最大長を求めよ。

解法

各点vのSubTreeで構成できるLIS長の最大値を考える。
その際以下の2つを考えよう。
f(v) := vのSubTreeの最後にvを選んだ時、それがLISの末尾になる。この時、LISに入れられるのは1つの子頂点の先の頂点群の番号のみである。
g(v) := vのSubTreeの最後にvを選んだ時、それがLISの末尾にならない。この時、LISに入れられるのは任意の子頂点の先の頂点群の番号である。

DFSで葉から順にf(v),g(v)を求めて行こう。

int N;
int P[101010];
vector<int> E[101010];

int dp[101010][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i+1];
		P[i+1]--;
		E[P[i+1]].push_back(i+1);
	}
	
	int ma=1;
	for(i=N-1;i>=0;i--) {
		if(E[i].size()==0) {
			dp[i][0]=1;
			dp[i][1]=0;
		}
		else if(E[i].size()==1) {
			dp[i][0]=dp[E[i][0]][0]+1;
			dp[i][1]=dp[E[i][0]][1];
		}
		else {
			FORR(e,E[i]) {
				//最長ケース
				dp[i][0]=max(dp[i][0],dp[e][0]+1);
				//和を取るケース
				dp[i][1]+=max(dp[e][0],dp[e][1]);
			}
		}
		
		//cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;
	}
	cout<<max(dp[0][0],dp[0][1])<<endl;
	
}

まとめ

もうちょい迷いそうなもんなのに、よくすんなり解いたな。