Codeforces Round 872 (Div. 2)

LuoTianyi and the Floating Islands (Hard Version)

算法本质

思维

题目大意

存在长度n的树（边权都是1），现在随机选择k个点建立房子。
定义中点：

• 点到所有房子的距离之和最短

输出中点个数的期望值。

思路推演

若某条边，两侧的房子数不相等，则一定会向更大数目的一侧移动。
这里也可以看出，若k是奇数，则中点一定在某个房子那，所以答案必定是1。

偶数则任何情况都不止1个点，因为其形式上的对称。
继续思考中点的本质：

• 周围任意子树的点数$<= \frac{k}{2}$

但是如果挨个点看待，这是一个至少目前无法解决的组合数问题。

回想条件，实际上奇数已经被求得，偶数并没有，能否用边的视角去看待问题。
如果希望这条边是可行的，则其两侧的点必须都是k/2：

• 这意味着可行的边是一条链
• 意味可行点数 = 可行边数+1

所以我们仅需寻找可行的边数即可，以边的视角来看待问题，随后问题变得异常简单。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
// 省略组合数板子极其初始化
int ans=0;
vector<int> g[maxn];
int dfs(int u=1, int ft=0)
{
    int res=1;
    for (int v:g[u])
    {
        if (v==ft)    continue;
        res += dfs(v, u);
    }
    ans += C(res, k/2) * C(n-res, k/2);
    ans %= mod;
    return res;
}
inline void solve()
{
    cin>>n>>k;
    for (int i=1; i<=n-1; i++)
    {
        int u, v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (k%2)        // 奇数特判
    {
        cout<<1<<endl;
        return;
    }
    dfs();
    // 这里的+1很关键，根据推测，每种情况下，可行点 = 可行边+1
    ans = ans * qpow(C(n, k), mod-2, mod) + 1;
    ans %= mod;
    cout<<ans<<endl;
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。