WARush

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

SRM674 Div1 Easy "VampireTree"

解法

まず木グラフの特性より、辺の数はn - 1なので、そうなっているか確認。(インプットのnumは辺を2回ずつ数え上げているから、(n - 1) * 2 = num[i]の合計値なのか確認)
木グラフになっていたら、あとはどう繋げればグラフの最大長が最大になるかだが・・・

どうもいろいろ試してみたところ、辺を2以上持つ頂点は、貪欲に直列につないでしまって問題ない。
そこに、辺を1だけ持つ頂点を補完するように繋いでいくことが必ずできる。
なぜかは理解してないけど、木グラフはそうゆう特性を持っているんだろうな~。

事後

問題文がTrue Ancestor(真の祖先)をやたらと強調するのは罠だったんですね!

ソースコード

class VampireTree {
    public:
    int maxDistance(vector<int> num) {
        int n = num.size();
        int sum = 0;
        int more2 = 0;
        for (int i = 0; i < n; i++) {
            sum += num[i];
            if (num[i] >= 2) {
                more2++;
            }
        }
        if ((n - 1) * 2 != sum) return -1;
        return more2 + 1;
    }
};