SRM 666 div1 easy:WalkOverATree
SRM 666 の練習です。本番でなくて良かった…(easy すらものすごい時間かかった)
解法
「基本的に一直線にある頂点に向かって行くけど, 別の頂点に訪れるために寄り道をすることもある」というように考えます。
すると, 寄り道する際に必要な移動回数は, (訪れる頂点の数) * 2 となります。
ある頂点 i の深さが d[i] であるとすると,
・L < d[i] ならその頂点に訪れることは不可能なのでスルー
・そうでない場合は, 寄り道できる頂点の個数は (L-d[i])/2 回
よって, i が最終地点のとき, 訪れることのできる頂点数は min(n, d[i]+1+(L-d[i])/2) 回となります。
i を全探索して答えを求めれば良いです。
const int MAXN = 55; vector<int> G[MAXN]; int d[MAXN]; void dfs(int v, int p, int depth) { d[v] = depth; for (int el : G[v]) { if (el == p) continue; dfs(el, v, depth+1); } } class WalkOverATree { public: int maxNodesVisited(vector <int> parent, int L) { int n = parent.size() + 1; for (int i = 0; i < n; i++) G[i].clear(); for (int i = 0; i < n-1; i++) { G[i+1].push_back(parent[i]); G[parent[i]].push_back(i+1); } dfs(0, -1, 0); int ret = 0; for (int i = 0; i < n; i++) { if (d[i] > L) continue; int tmp = d[i]+1; int plus = min(n-tmp, (L-tmp+1)/2); ret = max(ret, tmp+plus); } return ret; } }