题面和翻译来自洛谷，链接

题面翻译

给定一棵 $n$ 个结点的树，现在有 $k(k\le \min(n,3))$ 个结点上有人。

一个结点是好的当且仅当这个点到所有人的距离之和最小。

求在这 $n$ 个点中随机取 $k$ 个点时，好的结点的期望个数，对 $10^9+7$ 取模。

样例 #1

样例输入 #1

1
2
3
4
4 2
1 2
2 3
3 4

样例输出 #1

1
666666674

样例 #2

样例输入 #2

1
2
3
4
5
5 1
1 2
2 3
3 4
3 5

样例输出 #2

1
1

题解

首先对$k<=3$作分类讨论，不难发现$k=1$与$k=3$时数学期望只能是$1$，直接输出即可

$k=2$时好的节点是两个有人的节点本身加上连接它们的路径上的点，这种情况下的数学期望为所有不同的路径取法产生的好的点的数量总和/不同的路径取法数目

路径的取法明显有$\frac{1}{2}n(n-1)$种，如何求出这些路径经过的点的总和？

可以先求路径长度总和，每条路径的长度+1即为经过的点数

对于路径长度总和，可以换个角度从“每条边被走过了多少次”来考虑，dfs遍历过程中，将每条边两侧的节点数相乘（结果为有多少条路径经过这条边，即为这条边对总路径长度的贡献）再求和即可

由于求的是路径总长度，应再加上$\frac{1}{2}n(n-1)$，在求期望时可以直接在结果上+1

另外模运算的数学定义中，模的结果也必须是整数，乘法逆元需要进一步学习

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=2e6+10,mod=1e9+7;
// https://www.luogu.com.cn/problem/CF1824B1
LL n,k;
vector<LL> g[N];
LL ans;
LL s[N];

LL qmi(LL a,LL b,LL p){
    LL res = 1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

void dfs(LL u,LL p){
    s[u]=1;
    for(auto i:g[u]){
        if(i==p) continue;
        dfs(i,u);
        s[u]+=s[i];
        ans=(ans+s[i]*(n-s[i])%mod)%mod;
    }
}

int main(){
    fastIO
    cin>>n>>k;
    if(k==3||k==1){
        cout<<1<<endl;
        return 0;
    }
    for(int i=1;i<n;i++){
        LL a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,0);
    cout<<(ans*qmi(n*(n-1)/2%mod,mod-2,mod)%mod+1)%mod<<endl;
    return 0;
}