模拟赛题讲解[15]

来自 yukuai26 2022-08-07 noi.ac #2763

题目描述：

幻想乡有 $n$ 个建筑，每个建筑里住了一些居民。

有一些双向道路连接居民的家，共有 $n-1$ 条道路，恰好让所有居民的家能够互相到达。

其中标号为 $i$ 的建筑居住了 $i$ 名幻想乡的居民。

现在居民想要互相拜访，但是一次拜访需要花费 $\text{dis}(u,v)$ 的代价，其中 $u,v$ 分别是两人所在的建筑，$\text{dis}$ 表示这两个建筑之间的最短路。

⑨想要知道, 所有幻想乡人都拜访其他人所需要的代价之和。

答案对 $10^9+7$ 取模。

输入格式：

第一行一个整数 $n$。

接下来 $n-1$ 行, 每行 $2$ 个整数 $n-1$ 个整数描述 $n-1$ 条道路。

输出格式：

一个整数，表示总花费之和。

输入1：

输出1

数据范围：

对于 $30\%$ 的数据，满足 $n≤200$

对于 $60\%$ 的数据，满足 $n≤3000$

对于 $100\%$ 的数据，满足 $n≤1000000$

题解：

直接去算是 $O(n^2)$ 的，显然这是不可接受的

注意到询问是问的总和，因此我们可以考虑每条边的贡献

考虑一条边会被经过几次，它就会贡献多少

显然会经过

$s_u \times (S-s_u)$

其中 $S=\sum_{1\le i \le n} i,~~s_u = u+\sum_{v \in \text{son}(u)}v$

然后把每条边都加上就好了

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)

const int p=1e9+7;
int n,res,sum[N],S;
vector<int> g[N];
void add(int &x,int y){x=(x%p+y%p)%p;}
void dfs(int u,int f)
{
    sum[u]=u;
    for(int v : g[u])
    {
        if(v==f) continue;
        dfs(v,u);
        add(sum[u],sum[v]);
    }
    add(res,sum[u]%p*(((S-sum[u])%p+p)%p)%p);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);
    for(int i=1,u,v; i<n; i++)
    {
        read(u); read(v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1; i<=n; i++) add(S,i);
    dfs(1,1);
    write((res%p+p)%p); pc('\n');
    return 0;
}