# 主要思想

WQS 二分也叫带权二分，主要解决一类凸包上的问题。

假设当前你有一个很难计算的凸函数 $f(x)$ ，此时你要计算一个指定的 $f(n)$ ，如何快速求出呢？

我们可以去二分一个斜率 $k$ ，然后计算斜率为 $k$ 的一条直线落到这个凸壳上时的交点。

设这个交点为 $(x, f(x))$ ，再设函数 $g(k)$ 表示表示斜率为 $k$ 的直线落到凸壳上时的截距。

那么：

$f(x) = g(k) + kx\\ g(k) = f(x) - kx$

由于 $g(k)$ 是一条直线，感性理解一下，我们在计算这条直线上的值时就不需要考虑原题中的限制条件了。

于是我们就可以通过二分斜率来快速的找出答案了。

可以通过下面的例题来理解一下。

# 例题

# Description

P4383 [八省联考 2018] 林克卡特树

# Solution

首先转化一下题意，删边再加边显然是我们不想看到的，所以我们可以理解为从这棵树中选择 $k + 1$ 条不相交的链，使它们的权值和最大。

我们先推出 60pts 的暴力 dp。

设 $dp[0/1/2][x][i]$ 表示以 $x$ 为根的子树中选择 $i$ 条完整链， $x$ 点的度数分别为 $0/1/2$ 时的最大权值和。

然后分 3 种情况讨论：

$x$ 点度数为 0，那么此时 $x$ 不在链上，于是合并一下子树的权值即可。
$dp[0][x][i] = \max(dp[0][x][j] + dp[0][y][i - j])$
$x$ 点度数为 1， $x$ 可能本身是一条链上的端点，或者当前从儿子连上来一条边，如果连上来一条边的话要记得加上边权。
$dp[1][x][i] = \max(dp[1][x][j] + dp[0][y][i - j], dp[0][x][j] + dp[1][y][i - j] + w_{x, y} )$
$x$ 点度数为 2，这时也会有两种情况， $x$ 本身就是在一条链的中间，或者 $x$ 本身是一条链的端点， $y$ 也是一条链的端点，然后把 $x$ 和 $y$ 连到一起，注意也要加上边权。
$dp[2][x][i] = \max(dp[2][x][j] + dp[0][y][i - j], dp[1][x][j] + dp[1][y][i - j] + w_{x, y} )$

最后合并：

$dp[0][x][i] = \max(dp[1][x][i - 1], dp[2][x][i])$

答案就是： $dp[0][1][k]$

这样的复杂度是 $O(nk^2)$ 的，显然无法通过此题，考虑优化。

~~不难发现~~， $dp$ 值是一个上凸函数，这时 WQS 二分就登场了。

我们二分一下斜率 $mid$ ，每次暴力计算一下斜率为 $mid$ 的直线的值，这时没有了 $k$ 条边的限制，我们可以 $O(n)$ 计算出 $dp$ 值。

然后计算切点的位置，如果在 $k$ 左边，斜率变小，反之斜率变大。

于是这题就可以在 $O(n\log k)$ 的复杂度内完成啦。

# Code

mark

	#include <bits/stdc++.h>
	#define ll long long

	using namespace std;

	namespace IO{
	inline ll read(){
	ll x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const ll N = 3e5 + 10;
	ll n, k, tot, mid;
	struct node{
	ll v, w;
	};
	vector <node> g[N];

	struct data{
	ll val, cnt;
	inline bool operator < (const data &b) const {return val != b.val ? val < b.val : cnt < b.cnt;}
	inline data operator + (const data &b) const {return (data){val + b.val, cnt + b.cnt};}
	inline data operator + (ll b) const {return (data){val + b, cnt};}
	}dp[3][N];

	inline data upd(data b) {return (data){b.val - mid, b.cnt + 1};}//y 合并到 x 上，对于 x 来说多了一条链

	inline void dfs(ll u, ll fa){
	dp[2][u] = max(dp[2][u], (data){-mid, 1});
	for(auto y : g[u]){
	if(y.v == fa) continue;
	dfs(y.v, u);
	dp[2][u] = max(dp[2][u] + dp[0][y.v], upd(dp[1][u] + dp[1][y.v] + y.w));
	dp[1][u] = max(dp[1][u] + dp[0][y.v], dp[0][u] + dp[1][y.v] + y.w);
	dp[0][u] = dp[0][u] + dp[0][y.v];
	}
	dp[0][u] = max(dp[0][u], max(upd(dp[1][u]), dp[2][u]));
	}

	inline ll solve(){
	ll l = -tot, r = tot, res = 0;
	while(l <= r){
	mid = (l + r) >> 1;
	memset(dp, 0, sizeof(dp));
	dfs(1, 0);
	if(dp[0][1].cnt >= k) l = mid + 1, res = mid;
	else r = mid - 1;
	}
	memset(dp, 0, sizeof(dp));
	mid = res, dfs(1, 0);
	return res * k + dp[0][1].val;
	}

	signed main(){
	n = read(), k = read() + 1;
	for(ll i = 1; i < n; ++i){
	ll u = read(), v = read(), w = read();
	tot += abs(w);
	g[u].push_back((node){v, w}), g[v].push_back((node){u, w});
	}
	write(solve()), puts("");
	return 0;
	}

# End

dp 树形dp 分治