ABC173 F - Intervals on Tree

F - Intervals on Tree

解法

コンテスト中にここまで気づけるようになりたい（この回はEで苦戦してFを見ていませんが…）．

与えられるのは木であり，閉路が存在しない． よって，辺がない状態から辺を1つ増やすと，連結成分が必ず1つ減ることがわかる．

まったく辺がないときの連結成分の個数の合計は，

です．左辺から右辺を出すのに，wolframalphaの力を借りました．

上を計算したら，各辺が含まれる回数をそれぞれ引いてあげれば答えです． である各辺について，は，1からまでLが取れます．そしては，からNまでRが取れるので， 各辺が含まれる回数はそれぞれです．

提出コード

def main():
    N = int(input())
    ans = N*(N**2 + 3*N + 2)//6
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        if a > b:
            a, b = b, a
        ans -= a*(N-b+1)
    print(ans)


if __name__ == '__main__':
    main()

---

コンテスト終了直後のTLを見て，解法を理解しました．特にしゅんしゅんさんありがとうございます． ちなみにTwitterでコンテスト終了直後のTLを後から見たいときは， "filter:follows since:2020-07-05_22:40:00_JST until:2020-07-05_22:45:00_JST F問題"などと検索をかけるといいです．

自力ではサンプルとして，

5
1 2
1 3
2 4
2 5

を実験し，L=3のときのを観察していて，ようやくに気づけました．そのあと辺の数を引けばいいのはわかりましたが，上手く計算できず…．

入力サイズからO(N²)が間に合わないので，f(L,R)を愚直に計算することはないな～とは最初に思っていましたが，ここまでスッキリとした解法だとは思いませんでした．木ゆえに閉路はないという性質が効いてるのが好きです．うーん、やっぱりコンテスト中に解きたかった（E問題さん…）．