CF1824B1 LuoTianyi and the Floating Islands (Easy Ver.) 题解

FFTotoro · 2023-05-09 19:50:50 · 题解

前言

这场的 C 把我蓝名搞没了，这么简单的 D1 居然没看……

解法

如果 k=1 或 k=3，那么“好岛”只可能有且仅有 1 个：k=1 显然“好岛”就是选定的那个岛；k=3 时，若 3 个岛在同一条链上，“好岛”就是中间的那个岛，否则 3 个岛中间围住的部分形成了一个“人”字形，“好岛”即为“人”字中的那个分叉处的岛。

现在考虑 k=2 的情况：

首先有个性质，连接选定的 2 个岛的简单路径上的所有岛肯定都是“好岛”。

考虑如何借助这个性质解题；尝试对于每个岛处理，如果令这个岛（设为 x）为根结点上的岛，设 x 有 s 个儿子，那么从这 s 个儿子结点所管辖的 s 棵子树中选择两棵子树，再从两棵子树中各选择 1 个岛，这两个岛的简单路径必过 x。当然，还有可能 x 在那条链的一端，最后输出的时候加上对应的贡献即可。

那么，问题来了：如果不考虑 x 在链的一端的情况，如何计算以 x 为根时的选择儿子方案数？显然的，令 x 的 s 个儿子所管辖的子树大小为 e_1,e_2,\ldots,e_s，答案即为：

显然的，\left(\sum\limits_{i=1}^se_i\right)^2 即为 (n-1)^2，至于平方和（即第二个 \sum）可以用一遍 dfs 便捷地算出。

时间复杂度 O(n\log m)，这里 m=10^9+7（模数），\log m 为计算逆元的时间复杂度。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%mod*a%mod;
    a=a%mod*a%mod; b>>=1;
  }
  return r;
} // 快速幂，求逆元用
vector<int> g[200001];
int n,e[200001],w[200001];
// e[i] 为子树大小，w[i] 即为平方和
void dfs(int u,int r){
  e[u]=1;
  for(int i:g[u])
    if(i!=r){
      dfs(i,u),e[u]+=e[i];
      (w[u]+=e[i]*e[i]%mod)%=mod;
    }
  (w[u]+=(n-e[u])*(n-e[u])%mod)%=mod;
  // 计算出 w[i]
}
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int k,c=0; cin>>n>>k;
  if(k&1)cout<<"1\n"; // 答案必为 1
  else{
    for(int i=1;i<n;i++){
      int u,v; cin>>u>>v;
      g[u].emplace_back(v);
      g[v].emplace_back(u);
    }
    dfs(1,0); // 一遍 dfs
    for(int i=1;i<=n;i++)
      (c+=((n-1)*(n-1)%mod-w[i]+mod)%mod*qpow(2,mod-2)%mod)%=mod; // 算概率
    cout<<(c%mod*qpow(n*(n-1)/2%mod,mod-2)%mod+2)%mod<<endl;
    // 记得加上 2 的贡献（即 x 在链的一端的时候的贡献）
  }
  return 0;
}