洛谷 U140120 漂亮国大选

洛谷 U140120 漂亮国大选

洛谷传送门

题目背景

漂亮国是一个团结、民主的国家。

题目描述

这个国家有NN个城市，N-1N−1条双向道路连接着这些城市。因为漂亮国是一个团结的国家，所以从任何一个城市你都可以通过道路到达任何其他城市。是的，你是对的——漂亮国的拓扑结构是一棵没有方向的树。

漂亮国有很多党派，每个党派会“把控”一些道路。当然，每条道路只能被一个党派把控。

现在漂亮国要进行总统大选。在大选前，上一任总统有权重新安排所有道路的把控党派。上任总统安排道路的原则是：让整个国家看起来更民主。漂亮国国民对于民主的定义是：如果有一个党派拥有两条或以上的进入某个城市的道路，那么这个城市就不是一个民主的城市。

假设你是漂亮国国家道路安排局局长。总统希望，这样不民主的城市的数量不超过KK个。请你回答总统：最少需要多少个不同的党派把控道路？

输入格式

从文件election.inelectio**n.i**n中读入数据。

第一行两个整数N,KN,K，意义如题目描述所示。

接下来的N-1N−1行，每行两个整数u,vu,v，表示存在着一条从uu城市到vv城市的道路。

输出格式

输出到文件election.outelectio**n.out中。

一行一个整数ansans，表示最少所需党派数量。

---

命题背景：

预言梦：BIDEN WINS！

。。。找了好久的紫题，觉得挺好没细看就编成了题。结果其实是水题？

哭哭哭哭哭哭哭。

原题是打每条边的颜色，但是那需要SPJ，所以不想写了。就改了个题。越改越水。

不想改了，送大家分分吧。

也是练大家心态。

相信自己。

YY出的算法就是对的，不要因为它是T3就觉得它假了...其实真就是对的。

---

题解：

所以没啥可讲的，就是一贪心。

随便维护第二问就好。咋的都T不了。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e5+5;
int n,k,r;
int tot,head[maxn],to[maxn<<1],nxt[maxn<<1];
int cnt,ans[maxn];
void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
struct node
{
	int id,d;
}du[maxn];
bool cmp(node a,node b)
{
	return a.d<b.d;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		du[i].id=i;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
		du[x].d++,du[y].d++;
	}
	sort(du+1,du+n+1,cmp);
	r=du[n-k].d;
	printf("%d
",r);
	for(int i=n-k;i<=n;i++)
		if(du[i].d>r)
			ans[++cnt]=du[i].id;
	sort(ans+1,ans+cnt+1);
	for(int i=1;i<=cnt;i++)
		printf("%d ",ans[i]);
	puts("");
	return 0;
}