SRM666 Div1 Easy "WalkOverATree"
解法
一番深い葉ノードへ直進して(復路を戻ることはしない!)歩き終わるのが一番効率的であろう。
これは1の頂点につき1ステップかかる。
残りの枝道はどうあがいても1つの頂点につき2ステップかかる。
ソースコード
vector<int> G[55]; 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 v = 1; v < n; v++) { int u = parent[v - 1]; G[v].push_back(u); G[u].push_back(v); } // 深さ取得 int depth = dfs(-1, 0); int ans = 1; // まずは直進! int use = min(L, depth); ans += use; // そして往復! L -= use; ans += L / 2; ans = min(ans, n); return ans; } // 一番深い葉ノードへの距離を測る int dfs(int p, int c) { int res = 0; for (int i = 0; i < G[c].size(); i++) { if (G[c][i] == p) { continue; } res = max(res, dfs(c, G[c][i]) + 1); } return res; } };