AtCoder Beginner Contest 173 ABC173 F - Intervals on Tree

問題へのリンク

解説

まず、「閉路のない無向グラフにおいて、連結成分数 = 頂点数 - 辺数」が成り立つことを使います。

すると、問題は以下のように言い換えられます。

頂点数は

の計算でで求められます。は区間の長さです。

辺数に関しては、について考えるのは計算量が少なくともになってしまうので、数え上げの定石「主客転倒」をします。つまり、ある辺が何回寄与するかを考えます。 頂点とを繋ぐ辺が寄与する回数は、とが共に含まれるような区間の個数に等しいです。このような区間は、左端と右端がそれぞれ以上、以上となっています。よって、として寄与回数はになります。これを足し合わせて計算量はです。

実装

int main() {
    ll N;
    cin >> N;
    // \sum{連結成分数} = \sum{頂点数 - 辺数}
    // = \sum{頂点数} - \sum{辺数}
    // 主客転倒して考える
    ll ans = 0;
    for(int i = 1; i <= N; i++){
        ans += i * (N - i + 1);
    }
    rep(i,N-1){
        ll u, v;
        cin >> u >> v;
        if(u > v)swap(u,v);
        //この辺が選ばれる回数
        ans -= u * (N - v + 1);
    }
    cout << ans << endl;
}