题解：CF2167F Tree, TREE!!!

· · 题解

:::info[题目前的观察] 我们观察到，一个节点能作为 k 个节点的 lca 的充要条件是其子树大小 (含本身)\geq k。 :::

根据我们的观察，那么我们只需要求出一定不可能成为 lca 的节点，再对其求关于整棵树的补集的点数即可。\ 在这里我的实现是先将以 1 为根的情况统计出来，再进行换根操作，不难看出，其实质是对树的旋转。\ 具体步骤如下：\ 1、如果 sz_{fa} < k，那么 fa 原本是小于 k 的，换根后 fa 不再是根，它的子树大小会变化，先去掉它。\ 2、fa 的子树大小减少 sz_u。\ 3、更新 fa 的新子树大小是否小于 k，如果新大小 < k，则 fa 应被计入 cur（子树大小 < k 的节点）。\ 4、如果 sz_u < k，u 原本小于 k，现在要加上 sz_{fa}，所以先去掉它。\ 5、sz_u += sz_{fa}：更新 u 的子树大小。\ 6、更新 u 的新子树大小是否小于 k，方法同步骤 3。

:::align{center} ……不怎么华丽的分割线…… :::

至此，我们已经求出了 ans 数组，即 \forall i \in [1,n],ans_i = " 以 i 为根的树中不可能成为 k 个节点的 lca 的点的个数 "。\ 那我们只需要求 \sum_{i=1}^{n}n - ans_i 即 n^2-\sum ans 即可。

:::info[代码]

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e6 + 10;
int n,k;
vector <int> G[N];
int sz[N],ans[N];
int dfs(int u,int fa)
{
    sz[u] = 1;
    int cnt = 0;
    for(int v : G[u])
    {
        if(v == fa)
            continue;
        cnt += dfs(v,u);
        sz[u] += sz[v];
    }
    if(sz[u] < k)
        cnt++;
    return cnt;
}
void rotate(int fa,int u,int &cur)
{
    if(sz[fa] < k)
        cur--;
    sz[fa] -= sz[u];
    if(sz[fa] < k)
        cur++;
    if(sz[u] < k)
        cur--;
    sz[u] += sz[fa];
    if(sz[u] < k)
        cur++;
}
void rt(int u,int fa,int cur)
{
    ans[u] = cur; 
    for(int v : G[u])
    {
        if(v == fa)
            continue;
        rotate(u,v,cur);
        rt(v,u,cur);
        rotate(v,u,cur);
    }
}
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        long long res = 0;
        cin >> n >> k;
        for(int i = 1;i <= n;i++)
            G[i].clear();
        for(int i = 1;i < n;i++)
        {
            int u,v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        int init = dfs(1,0);
        rt(1,0,init);
        for(int i = 1;i <= n;i++)
            res += ans[i];
        cout << 1ll * n * n - res << '\n';
    }
    return 0;
}
/*
1
5 3
1 2
1 3
1 4
1 5
*/

:::

:::align{center} 完结撒花！ :::