AT_abc173_f Intervals on Tree 题解

· · 题解

Intervals on Tree

考虑点边容斥。

因为初始是一棵树，所以最后构成的一定是若干棵子树。

每一个子树中，点的数量都是边的数量加 1。

所以连通块数量就是点的数量减边的数量。

点的数量

对于区间 [l,r]，此时一共有 (r-l+1) 个点。

所以点的数量之和：

\sum_{l=1}^{n}\sum_{r=l}^{n}(r-l+1)\\ =\sum_{l=1}^{n}(1+2+\cdots+(n-l+1))\\ =\sum_{i=1}^{n}i(n-i+1)

从第二行推导到第三行是因为考虑 1 在 l\in[1,n] 中被计算，2 在 l\in[1,n-1] 中被计算，以此类推。

边的数量

如果有一条边 (u,v)，不妨假设 u<v。

那么这一条边被连上等价于当前区间 [l,r] 满足 l\le u 且 v\le r。

这样满足条件的区间一共有 u(n-v+1) 个。

所以最后的答案：

Ans=\sum_{i=1}^{n}i(n-i+1)-\sum_{(u,v)\in E}u(n-v+1)

其中假设 u<v。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+5;
int n,ans;
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        ans+=i*(n-i+1);
    }
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        if(u>v)swap(u,v);
        ans-=u*(n-v+1);
    }
    cout<<ans<<"\n";
}