[CF2167F] Tree, TREE!!! 题解

先考虑

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

对答案的贡献。

时间复杂度线性。

code

CPP

#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;
}

[CF2167F] Tree, TREE!!! 题解

文章操作

相关推荐

评论

[CF2167F] Tree, TREE!!! 题解