Intervals on Tree [AtCoder Beginner Contest 173 F]

https://atcoder.jp/contests/abc173/tasks/abc173_f

解説

https://atcoder.jp/contests/abc173/submissions/15025119

さて、まずはf(L,R)というのが提示されているので、これについて考えていこう。

f(L,R)

連結成分の個数についての典型がある。
閉路が存在しないならば「連結成分の個数 = 頂点数 - 辺の数」が成り立つ。
競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん
まあ、よーく観察してみると確かにとなるのだが、これを知っているとそうでないとでは、だいぶ初動に差が出ると思う。
つまり、以下のように変換して考えることができる。
f(L,R) := (R-L+1) - (両端が[L,R]にある辺の個数)
よって、求めたい答えは
((R-L+1)の二重和) - ((両端が[L,R]にある辺の個数)の二重和)
と考えられる。

(R-L+1)の二重和

これは単純で、Lを全探索してみると、
L=1のとき、1,2,3,4,...,Nであり、N(N+1)/2
L=2のとき、1,2,3,...,N-1であり、(N-1)N/2
...
L=Nのとき、1であり、1
みたいに初項1公差1の等差数列の和を順番に計算して、足し合わせていけばいい。

(両端が[L,R]にある辺の個数)の二重和

問題はこっちであるが、主客転倒テクを使おう。
「全ての区間に対して、両端が[L,R]にある辺の個数を求める」と間に合わないが、
「全ての辺に対して、その辺が何通りの区間に含まれるか」を計算することにしよう。

分からない人向けに言い回しを少し変えて書いておく。
- 全ての区間に対して、「両端がその区間に含まれる辺の個数」の総和
- 全ての辺に対して、「その辺が含まれる区間の個数」の総和
この2つは結果が同じになる。

なので、ある辺に対して、その辺が含まれる区間の総和は、辺の両端をU<Vと仮定すると、
区間[L,R]は
- 1≦L≦U
- V≦R≦N
を満たす必要があり、かつ、これを満たしていれば必ず含む。
なので、
- 1≦L≦U → U通り
- V≦R≦N → N-V+1通り
なので、U*(N-V+1)通りが「その辺が含まれる区間の個数」である。
あとは、これの総和を取ると、(両端が[L,R]にある辺の個数)の二重和が得られる。

これで「((R-L+1)の二重和) - ((両端が[L,R]にある辺の個数)の二重和)」が求められるのでAC

int N, U[201010], V[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) cin >> U[i] >> V[i];

    ll ans = 0;
    rep(L, 1, N + 1) ans += 1LL * L * (L + 1) / 2;
    rep(i, 0, N - 1) {
        if (U[i] > V[i]) swap(U[i], V[i]);
        ans -= 1LL * U[i] * (N - V[i] + 1);
    }
    cout << ans << endl;
}