题解：CF2167F Tree, TREE!!!

题目前的观察

我们观察到，一个节点能作为

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。

……不怎么华丽的分割线……

至此，我们已经求出了

ans

数组，即

\forall i \in [1,n],ans_i

= " 以 i 为根的树中不可能成为 k 个节点的 lca 的点的个数 "。
那我们只需要求

\sum_{i=1}^{n}n - ans_i

即

n^2-\sum ans

即可。

代码

CPP

#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
*/

完结撒花！

题解：CF2167F Tree, TREE!!!

文章操作

相关推荐

评论

题解：CF2167F Tree, TREE!!!