.keys 抜けが１つと L[] 抜けが３つだけと実装も素直。根からの距離を BIT で、LCA をダブリングで求めた。根からの距離をセグメント木で管理するなら LCA もセグメント木で求めたらいいと思う。BIT+セグメント木は無駄だし面倒すぎるのでナシ。だってセグメント木は BIT の上位互換でしょ？■提出 #39951562 (TLE×24)。試しにセグメント木で根からの距離の累積和と LCA の両方を管理してみたら派手に TLE だった。累積和は BIT でやる方が軽いのかな。■提出 #39954631 (AC / 3966 ms)。頑張りました。セグメント木にダミーの０番目の要素を入れて添字計算の微調整を省いたり、&:method 形式は Symbol#to_proc が呼ばれるせいなのか知らないけどやや遅いみたいなのでブロックを渡すようにしたり、せっかくセグメント木で累積和を管理しているのだから根からの距離を求めてから LCA を引き算するのでなく LCA からの距離を直接求めたり、オイラーツアーで作成する配列のサイズが 3N くらいになっていたのを節約して 2N に抑えたり。最初の AC だったなんちゃって HLD よりよっぽど厳しい。■モノイドが乗せられるようにまじめに ST クラスを改良したので、クラスを書く時のマイルールを。まずクラス利用者が知りたいであろう public インターフェイスを書いてから部外秘である private メソッドを並べる。public メソッドの中では、最初に呼ばれるであろうコンストラクタ(イニシャライザ)をまず書いて、つぎにアクセサ(読み取りメソッド)を書く。最後に、なくてもいい存在であり有害にもなり得るので書きたくないミューテータ(内部への働きかけ)を書く。クラスはオブジェクトのテンプレートであり、型通りの処理(不変部分)を書く場所だけど、ではオブジェクトのアイデンティティがどこにあるかというとコンストラクタへの引数でありインスタンス変数(メンバ変数)にふるまいを変える固有の値(可変部分)がある。すべてのメソッドがインスタンス変数に依存するべきだというのはそのため。その依存がないならメソッドの置き場所が間違っているサイン。とかとかいうことを考えながらクラスを書いている。あとはまあ名前だよね。よく言われるように名前重要。ソフトウェアという形のないものにはっきりした輪郭を与えるのは名前。適切な名前さえあればその実体をどう実装するかはどうとでもなるしどうでもいい。好きに、うまくやればいい。コーディング対象として適切な抽象に紛れのない輪郭を与える唯一無二の名前を見出すところが決定的に重要(形容詞増し増しで強調しました)。自分が常々疑問なのは、変数名に型名を使うというひとつの典型パターン(var arr = new Array; みたいな)。そりゃね、飼ってる猫が１匹だけならその呼び名はネコでも十分わかりますけどね、それは消去法や文脈でそう判断できるというだけであって、直接的な命名ではない。解釈や判断という余計なステップ、疑問や誤解の入り込む余地がある。クラスではなくインスタンスの、それそのものの本質を掴んだ命名をするのだ。■いやでも適切な命名は文脈に依存するということも言えるんだよな。識別子が機能するためには他と区別するのに十分な長さを必要に応じて使うのでいい。１文字変数を使い切ってから２文字３文字変数を使う、みたいな。ハフマン符号的な。その対極がたぶん Java の説明的で長ったらしい命名で、自分は HTML の p タグとか好きでいっぱい使いたくなる人間だからどちらかといえばアンチ Java なんだな。そのくせ、よそ者として文脈を共有しないで他人が書いたコードを眺めてるときに限って「変数名に型名を使ってる」とかを批判的に見てしまうわけだ。勝手な。