[CF2167F] Tree, TREE!!! 题解

aeiouaoeiu · 2025-11-19 11:26:52 · 题解

先考虑 u 在 S_r 内需要满足的条件，首先在选择 LCA 时不能选在 u 子树外的点，否则 LCA 只能为 u 的祖先。接下来可以强制钦定 u 被选择，那么只要接下来选的点都在 u 子树内，LCA 就必然是 u。于是需要满足 k 个点能在 u 子树内选完，即 \text{siz}_u\ge k。

考察 \text{siz}_u 在根变化时会如何变化。令根为 1，得到此时 u 子树大小 \text{siz}_u。

• 若 r 在 u 的儿子 v 的子树内，则 \text{siz}'_u=n-\text{siz}_v，一共有 \text{siz}_v 个这样的 r；
• 若 r 在 u 的子树外，则 \text{siz}'_u=\text{siz}_u，一共有 n-\text{siz}_u 个这样的 r；
• 若 r=u，则 \text{siz}'_u=n。

于是可以轻松求出 u 对答案的贡献。

时间复杂度线性。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
#define pob pop_back
using namespace std;
typedef long long ll;
const ll maxn=200007,ee=1e18;
ll n,k,siz[maxn],ans;
vector<ll> edge[maxn];
void dfs(ll u,ll fa){
    siz[u]=1;
    for(auto v:edge[u]){
        if(v==fa) continue;
        dfs(v,u),siz[u]+=siz[v];
        ans+=siz[v]*(n-siz[v]>=k);
    }
    ans+=(n-siz[u])*(siz[u]>=k);
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        for(ll i=1;i<=n;i++) edge[i].clear();
        cin>>n>>k,ans=n;
        for(ll i=1,u,v;i<n;i++){
            cin>>u>>v;
            edge[u].pb(v),edge[v].pb(u);
        }
        dfs(1,0);
        cout<<ans<<"\n";
    }
    return 0;
}

::::