[Atcoder] 木の問題

https://cf16-relay-open.contest.atcoder.jp/tasks/relay_k

概要

  • 問題文がそれなりに読みにくい。
  • いわんとしていることは、選んだ頂点については2回通ってはならないということである。この状況で選ぶ頂点の数を最大化すれば良い。
  • 答えは木の直径以上になることは容易に想像がつく。

考察

  • 枝分かれする(辺が3本以上ある)頂点については、つながっている辺の先にある葉(辺が1本ある頂点)を選んだほうが良いのは明らかである。
  • 問題は辺がちょうど2本ある頂点であるが、木の直径上にある頂点を選ぶ方法でサンプルは通る。
  • しかし、たとえばこういう入力の場合、sub-optimalになってしまう。
1
2
3
4
5
6
7
8
9

o-o-o-o-o
    |
  o-o-o
    |
  o-o-o
    |
  o-o-o
    |
    o
  • 対処するには、木の直径を求めるコードを変形し、頂点の重みを、辺が2本ある場合のみ1に、それ以外は0とすれば良い。

解答例

感想

  • これを時間内に思いつくのはやはりすごいと思いました…