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