WQS二分
一句话：对于凸包，二分一个直线l的斜率k使得l与凸包的切点所对应的x为题目要求的x。此时y(也就是f(x))加或减kx就是答案。
适用范例：
- 如果不思量选的物品的个数限制，可以很快求出答案。
- 恰好选 k 个物品的最优代价
思路：
思量不限制，那我们肯定可以求到一个最优值。而这个值的两侧一定不优于它。这样大概是一个凸包（？）（不会凸包，好像要打表什么的发现）。
思量一个直线与凸包的切点一定是当前斜率的最优值。为什么？我们知道 \(y=kx+b\) ，\(y\) 就是 \(f(x)\) ,也就是 \(b=f(x)-kx\) 。观察 \(b\) 的形式(只要把每次得到的权值-=k,然后正常在求恣意次物品情况下的最优答案），发现截距 \(b\) 是我们要求的答案。由下图可知，相切时是最大值。
又因为，凸包切线的斜率是递增/递减的，上图为递减。所以可以二分斜率。
那么我们就通过二分斜率，使得直线与凸包相切在x=k的点上，求得答案。
例题：
P2619 [国家集训队] Tree I
思路:
不加 \(k\) 条白边限制的最小生成树肯定都会。加入我们求出来的最小生成树有 \(p\) 条白边。那么有3种情况。
- \(p=k\) RP++！（正好是答案）
- \(pk\) 同上。通过增加权值，去掉多余的白边。
而我们增加或镌汰的值，就是要二分的。二分权值后做最小生成树，求到最小权值使得答案满足。
如何用图像来明白呢？
\(x\)代表选白边数量，\(f(x)\) 为此时最小生成树权值。
这是一个下凸的凸包，斜率递增。
黄点是我们无限制时的最优值。绿点是要求的。所以我们通过二分斜率来求切到它时的截距。此中\(b=f(x)-kx\) ，\(k\) 就对应我们增减的权值。
code：
[code]#includeusing namespace std;const int N=1e5+3;int n,m,k;struct node{ int x,y,w,c;}e[N];int fa[N];int cnt,cw,sum;int ans;bool cmp(node a1,node a2){//注意！ if(a1.w!=a2.w) return a1.w |
