問題概要
N頂点の木が与えられる。各頂点には0または1が書かれている。好きな頂点を選び、そこに行き、以降以下の1.または2.の操作のいずれかを何回か行う。
- 隣接する頂点を一つ選び、移動し、移動先の頂点の数字を1->0または0->1に変更する。
- 現在いる頂点の数字を、1->0または0->1に変更する。
操作は任意の地点から始めることができ、また任意の地点で終えることができる。
全ての頂点に書かれた数字を0にしたい。操作回数の最小値を求めよ。
制約
N <= 100000
想定*誤答*
1が書かれた頂点だけを考えれば良い。操作の始点・終点は、1が書かれた頂点同士の間でもっとも遠いペアにすれば良い。それさえ決まれば、dfsでできる。
正解
まず、0が書かれた葉は関係ないので、全て削除する (queueで簡単)。この時残っている頂点のリストを作ると良い。
求める操作列は、Euler tour から単純パスを引いたものである。Euler tourについての操作列の長さは簡単。どのような単純パスを引けばいいかを考える。頂点vに書かれた数をc[v]とすると、単純パスを引くことによる操作回数への効用は、2 * #{v | c[v] xor (deg[v] % 2) } である(この値だけ操作回数が少なくなる)。これを最大化すればよい。最大化は木の直径を計算するのと同じアルゴリズムで、O(N)でできる。
感想
こういう難しい問題でも、数学的な分析ができるようになりたい。最初解く時に、始点と終点は最遠点同士だと決め打ちしたが、これにはなんの根拠もない。このような考察ミスをなくすのが大切。
おまけ
誤答 Submission #2531853 - AtCoder Regular Contest 097 は、c[v] = 0となる葉の削除にも手間取っている。「DFS をやってみて、c[v] = 1となる頂点に出会う前に元の頂点に戻ったら、そこより先はなかった扱いにする」ということをやっているが、これはやってはいけない。
解説をみた後の正答:
Submission #2532111 - AtCoder Regular Contest 097
