题目链接

题意分析

对于这道题 能留下大的尽量留下大的

我们以n为根 根是必选的

然后从大到小 如果当前点i未被留下 并且留下i到根n的所有点不会超过n-k 那么就全部留下

对于判断的话 由于一个点i被留下 那么i的祖先节点也会被留下

所以对于未被留下的点 我们使用倍增确定i往上最近的未被留下的点 复杂度O(nlogn)

然后暴力染色 由于每一个点只会被染色一次 所以复杂度是O(n)

CODE:

#include
#define M 2008611
#define INF 200080
using namespace std;
int n,k,tot,cnt;
int to[M],nex[M],head[M];
int dep[M],fa[M][22];
bool tag[M];
void add(int x,int y)
{to[++tot]=y;nex[tot]=head[x];head[x]=tot;}
void dfs(int now,int fat)
{
	dep[now]=dep[fat]+1;fa[now][0]=fat;
	for(int i=1;(1<=0;--i)
	{
		if((1<dep[tmp]) continue;
		if(fa[tmp][i]&&!tag[fa[tmp][i]]) tmp=fa[tmp][i];
	}
//	printf("now is to %d\n",tmp);
	return dep[now]-dep[tmp]+1;
}
void update(int now)
{
	while(tag[now]==0)
	{
		tag[now]=1;++cnt;
		now=fa[now][0];
	}
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1,x,y;i