SRM 666 Div1 Easy WalkOverATree

頂点 0 まで戻ってくる場合の問題について考える。
すると、無駄な探索をしなければ、L/2+1 個の頂点に到達することができる。
頂点 0 まで戻る必要が無い場合には、深さが最大となる頂点までの距離の分 (すなわち深さの最大値) だけ移動距離を増やせるため、L' = L+ max{depth} として、L'/2+1 個の頂点に到達できる。
頂点数が L に対して小さいときは、頂点数との min を取ることを忘れないことに注意する。

#define N 60
int d[N];

class WalkOverATree {
	public:
	int maxNodesVisited(vector <int> p, int L) {
		int m = p.size();
		rep(i, m) d[i+1] = d[p[i]]+1;
		int mx = 0;
		rep(i, m+1) chmax(mx, d[i]);
		if(mx>=L) return min(m+1, L+1);
		return min(m+1, (L+mx)/2+1);
	}
};