WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};