mayoko’s diary

プロコンとかいろいろ。

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