一、题目描述:
给定 $n$ 和 $k$，表示有 $n$ 个点，其中有 $k$ 个点是关键点，这 $k$ 个点随机分布。
给出 $n$ 个点的连接方式，保证构成一棵树，求有期望多少个点使得这个点到 $k$ 个关键点的距离之和最小，答案对 $1e9+7$ 取模。
数据范围：$1\leq n\leq 2e5，1\leq k\leq min(n,3)$。
二、解题思路：
$k=1:$
很明显答案是一，就是这个关键点本身，直接输出即可。
$k=2:$
两个关键点之间的路径长度$+1$就是关键点数量，统计路径被经过的次数即可。
$k=3:$
枚举每一个点，假设当前枚举到 $u$,考虑计算点 $u$ 是答案点的方案。
$Situation 1:点 u 是关键点$
那么这 $3$ 个关键点必然构成一条链，且点 $u$ 在中间，暴力计算即可。
$Situation 2:点 u 不是关键点$
那么 $3$ 个关键点必然不在一条链上，且在 $u$ 的不同子树中（假设 $u$ 是根），需要前缀和统计计算。
那么此题已经解决，时间复杂度 $O(n)$。
三、完整代码：
1 #include<iostream> 2 #define N 200010 3 #define lim 200000 4 #define to edge[i].v 5 #define ll long long 6 #define M 1000000007 7 using namespace std; 8 ll n,k,u1,v1,ans; 9 ll s[N],jc[N],inv[N],sum[N]; 10 struct EDGE{ 11 ll v,nxt; 12 }edge[N*2]; 13 ll head[N],cnt; 14 void add(ll u,ll v) 15 { 16 edge[++cnt].v=v; 17 edge[cnt].nxt=head[u]; 18 head[u]=cnt; 19 } 20 ll ksm(ll base,ll p) 21 { 22 ll res=1; 23 while(p) 24 { 25 if(p&1) res*=base,res%=M; 26 base*=base,base%=M,p>>=1; 27 } 28 return res; 29 } 30 void pre_work() 31 { 32 jc[0]=1; 33 for(ll i=1;i<=lim;i++) 34 jc[i]=jc[i-1]*i%M; 35 inv[lim]=ksm(jc[lim],M-2); 36 for(ll i=lim;i>=1;i--) 37 inv[i-1]=inv[i]*i%M; 38 } 39 void update(ll u,ll val) 40 { 41 ans+=val*(n-1)*(n-1-val)%M; 42 ans-=ksm(val,2)*(n-1-val)%M; 43 ans-=val*(sum[u]-ksm(val,2))%M; 44 ans=(ans%M+M)%M; 45 } 46 void dfs1(ll u,ll ff) 47 { 48 for(ll i=head[u];i!=-1;i=edge[i].nxt) 49 if(to!=ff) 50 { 51 dfs1(to,u), s[u]+=s[to]; 52 (sum[u]+=ksm(s[to],2))%=M; 53 } 54 s[u]++,sum[u]+=ksm(n-s[u],2)%M; 55 } 56 void dfs2(ll u,ll ff) 57 { 58 for(ll i=head[u];i!=-1;i=edge[i].nxt) 59 if(to!=ff) 60 (ans+=s[to]*(n-s[to])*2)%=M,dfs2(to,u); 61 } 62 void dfs3(ll u,ll ff) 63 { 64 update(u,n-s[u]),(ans+=3*(n-s[u])*(s[u]-1))%=M; 65 for(ll i=head[u];i!=-1;i=edge[i].nxt) 66 if(to!=ff) 67 { 68 update(u,s[to]);dfs3(to,u); 69 (ans+=3*s[to]*(n-s[to]-1))%=M; 70 } 71 } 72 void baoli() 73 { 74 dfs1(1,0);dfs2(1,0); 75 cout<<(ans+n*n-n)%M*ksm((n*n-n)%M,M-2)%M<<'\n'; 76 } 77 void rwork() 78 { 79 dfs1(1,0);dfs3(1,0); 80 cout<<ans*ksm((n*n-n)%M*(n-2)%M,M-2)%M<<'\n'; 81 } 82 int main() 83 { 84 cin>>n>>k; 85 pre_work(); 86 for(ll i=1;i<=n;i++) 87 head[i]=-1; 88 for(ll i=1;i<n;i++) 89 { 90 cin>>u1>>v1; 91 add(u1,v1); 92 add(v1,u1); 93 } 94 if(k==1) 95 { 96 cout<<1<<'\n'; 97 return 0; 98 } 99 if(k==2) baoli(); 100 if(k==3) rwork(); 101 return 0; 102 }
四、写题心得：
这个题是自己想出来的，很不错。可是很烦的一点就是比赛之后 $C$ 题居然 $Main$ $Test$ $Run$ $Time$ $Error$ 了，导致从 $1400$ 名掉到 $3500$ 名，还掉分了！
而且这个 $D1$ 我的一个同学写的比较简单，比我的代码短多了，还得继续加油才是啊！拜拜！