【SET求直径】Codeforces 1004E Sonya and Ice Cream

题面在这里

题意：给一棵带边权的树，求一条不超过k个点的链，使得所有点到链的距离的最大值最小

​

显然链在直径上，直接求直径，在直径上做滑动窗口即可

……

然而还有更妙的解法：

考虑每次删除一个叶子结点，最后得到一条链

要使这个最大值最小，每次删除的点对答案的贡献一定要最小

由于对答案贡献一定是递增的，所以贪心的正确性显然

用一个SET维护所有叶子结点，权值是子树中点到父亲的最大距离，即对答案的贡献

​

示例程序：

#include<cstdio> 
#include<set>
#include<algorithm>
using namespace std;

const int maxn=100005;
int n,K,f[maxn];
struct data{
	int x,w;
	data () {}
	data (int _x,int _w):x(_x),w(_w) {}
	bool operator<(const data&b)const {return w<b.w||w==b.w&&x<b.x;}
};
set<data> d[maxn],S;
int main(){
	scanf("%d%d",&n,&K);
	for (int i=1,x,y,z;i<n;i++)
	 scanf("%d%d%d",&x,&y,&z),
	 d[x].insert(data(y,z)),d[y].insert(data(x,z)),
	 f[x]++,f[y]++;
	for (int i=1;i<=n;i++)
	 if (f[i]==1) S.insert(data(i,(*d[i].begin()).w));
	int ans=0;
	while (n>K||S.size()>2){
		int x=(*S.begin()).x,fa=(*d[x].begin()).x,w=(*d[x].begin()).w;
		ans=(*S.begin()).w; S.erase(S.begin()); n--;
		f[fa]--; d[fa].erase(d[fa].find(data(x,w)));
		if (f[fa]==1) S.insert(data(fa,(*d[fa].begin()).w+ans));
	}
	printf("%d",ans);
	return 0; 
}