SRM 666 Div1 Easy - WalkOverATree

問題

TopCoder Statistics - Problem Statement

問題概要

頂点数がの木が与えられる。これらの頂点には~と番号が振られている。今、をスタート地点として、この木の上を移動することを考える。ステップの移動が許されている時に、訪れることのできる頂点数の最大値を求めよ。

• 
• 

アイデア

まず、ステップを最大限に利用したいと思うなら、一度通った辺はもう通らない一本道が一番効率が良いのは想像がつく。ステップで訪れる頂点を最大化したい時には、二度以上訪れる頂点はできるだけ少なくしたい。とりあえずこのような一本道で、最も長いものを考えてみると、を根とした木を考えた時に深さが最も深い頂点へと続く道がそれになる。この最も深い頂点の深さをとすれば、この一本道をステップで通過し、それによって個の頂点を訪れることが出来る。

このような一本道に対して、ならばこの一本道を辿る途中でステップが終了する。つまり、個の頂点に訪れることができるようになり、これ以上になることはないのでこれが答えとなる。

では、の値が大きい場合はどうなるだろうかと考えてみると、この一本道から寄り道するような感覚で考えると、どこかの頂点から行って戻るという動作が加わるので、一本道から外れる頂点へとずれるには1頂点あたり絶対に2ステップが必要になる。寄り道のために残されたステップはであるから、これを2で割った数を切り捨てて加算してあげればよい、ということになる。もちろん、これがを超えることはないのでそこで決め打ちしておく。

一本道のところまでは考えたけどちょっと複雑に考えすぎた。グラフ、特に木とか閉路の問題苦手...

実装(C++)

class WalkOverATree {
    public:
    int maxNodesVisited(vector<int> parent, int L) {
        int n=parent.size()+1;

        //各頂点の深さを調べる
        int d=0;
        for(int i=1; i<n; ++i)
        {
            int ct=1;
            int now=i;
            while(parent[now-1]!=0)
            {
                now=parent[now-1];
                ++ct;
            }
            d=max(d,ct);
        }

        int ret=L+1;
        if(d<L) ret=min(n,d+1+(L-d)/2);
        return ret;
    }
};