問題概要
考えたこと
なんとなく、親ノードに遡りながら状態をまとめていけばよさそう。
当初、特殊辺を二つの木に対して同時に親ノード側に伸張することを考えたが、二つの特殊辺が片方の木でのみ接続するパターンに対する数え上げパートが原因でTLEした。
しばらくして、特殊辺の伸張はもう一方の木に対して独立に行うことができることに気付く。
二つの木をそれぞれ $ A, B $ とし、$ i $ 番目の特殊辺を $ ( a_i, b_i ) $ とすると、$ A $ に対して $ x $ 回、$ B $ に対して $ y $ 回親ノード側に遡った拡張特殊辺は $ ( a_i $ >> $ x, b_i $ >> $ y ) $ と表すことができる。
サイクルの積は、二つの拡張特殊辺 $ ( u, v ), ( u \, xor \, 1, v \, xor \, 1 ) $ を結ぶときに数え上げればよい。
拡張特殊辺をまとめるパートは、各 $ u $ に対して $ v $ を列挙する方法において、
- $ v, v \, xor \, 1 $ -> $ ( v $ >> $ 1 ) $ : そのまままとめる
- $ u, u \, xor \, 1 $ -> $ ( u $ >> $ 1 ) $ : マージソートの要領でまとめる
とすれば計算が間に合う。
各 $ x, y $ に対して拡張特殊辺の数は高々 $ 2 ^ H $ 本なので、計算量は $ O ( H ^ 2 ･ 2 ^ H ) $ である。
提出コード
空間計算量の改善を図った結果とても見づらいコードになってしまった（いつも通り）。
