LOJ#2478. 「九省联考 2018」林克卡特树

### 题目描述
小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做 “LCT” 的挑战，它的规则是这样子的：现在有一个 NN 个点的树（Tree），每条边有一个整数边权 $v_i$，若 $v_i \ge 0$，表示走这条边会获得 $v_i$的收益；若 $v_i \lt 0$，则表示走这条边需要支付 $−v_i$ 的过路费。小 L 需要控制主角 Link 切掉（Cut）树上的恰好 $K$ 条边，然后再连接 $K$ 条边权为 $0$ 边，得到一棵新的树。接着，他会选择树上的两个点 $p, q$ ，并沿着树上连接这两点的简单路径从 $p$ 走到 $q$ ，并为经过的每条边支付过路费 / 获取相应收益。

海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从而使总收益-总过路费最大化的话，就把传说中的大师之剑送给他。

小 L 想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link 能得到的总收益-总过路费最大是多少。

输入格式
输入第一行包含两个正整数 $N, K$，保证 $0 \le K \lt N \le 3 \times 10^5$。

接下来$ N − 1 $行，每行包含三个整数 $x_i, y_i, v_i$，表示第 $i$ 条边连接图中的 $x_i, y_i$两点，它的边权为 $v_i$。

输出格式
输出一行一个整数，表示答案。

样例
样例输入 1
```
5 1
1 2 3
2 3 5
2 4 -3
4 5 6
```
样例输出 1
```
14
```
样例解释 1
一种可能的最优方案为：切掉 $(2, 4, −3)$ 这条边，连接 $(3, 4, 0)$ 这条边，选择 $(p, q) = (1, 5)$。

样例 2
见附加文件中的 lct/lct2.in 与 lct/lct2.ans。

数据范围与提示
对于 $10\%$ 的数据，$k = 0$;

对于另外 $10\%$ 的数据，$k = 1$;

对于另外 $15\%$ 的数据，$k = 2$;

对于另外 $25\%$ 的数据，$k \le 100$;

对于其他数据，没有特殊约定。

对于全部的测试数据，保证有 $1 \le N \le 3 × 10^5$
 , $1 \le x_i, y_i \le N$, $|v_i| \le 10^6$。

↓这不是作者加的是原题就有的，毒瘤出题人写的提示。

提示：题目并不难。
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
## 思考时间 ♫♪
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$
$\space$

## <font color=white> 标签里看不到算法的，别想了 </font>

原问题太过抽象，我们先把原来的问题转化一下。

不难发现，我们要做的其实等价于把原树分割成$k + 1$棵树(一个森林)，然后使它们的直径和最大。

但是这个也不太好做。

我们发现我们并不关心树的分割方案，我们关心的只是直径。那么直接考虑直径本身。发现等价于在树上选出$k + 1$条互不相交的链使得链长最大。

这时候我们就有一个$O(n^2)$的$dp$做法了，考虑$f(i,j,0/1)$表示在$i$这个子树中的情况已经处理完了，选了$j$条链，$0/1$表示根是否接通。

那么对于$100\%$的部分分，怎么办呢？

观察到$j$这一维具有凸性，如果把每一次链的选择带上一个额外代价$cost$(*注意$cost\in [-inf,inf]$可以为负)的话就可以控制划分的次数。

带权二分？！

会带权二分的同学可以跳过下面这一段了

-----
我们先考虑，如果没有链个数的限制，那么只选正的一定是最优决策。

于是，为了不让它只选正的，我们给每一次选择的操作一个代价$cost$。我们发现，最优决策选择链的个数一定随着$cost$的递增而递减，当$cost=+\infty$时，没有一段会被切开。具有单调性。

单调性？二分？

$Wow!$，我们可以通过二分$cost$的大小来控制选择的链个数是否为$K+1$!
简单来说，我们二分一个$cost$，判断最优决策下选择链个数的最大值是否大于$K+1$，如果个数偏大我们把$cost$调大，反之我们把$cost$调小。

但是要注意一点：因为在带权二分中，必须满足选择的链个数数也是单调的。每次$dp$我们需要在保证解最优的情况下再使取得的链的个数最大/最小。

-----

然后就做完啦~

聪明的你有没有AC这道清真的好题呢？

```
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 3e5 + 5;
const LL inf = 0x3f3f3f3f3f3f3f3f;
struct edge {
	int v, w, next;
} e[maxn << 1];
int head[maxn], cnt, n, u, v, w, k;
int blk[maxn][2];
LL dp[maxn][2];

void adde(const int &u, const int &v, const int &w) {
	e[++cnt] = (edge) {v, w, head[u]};
	head[u] = cnt;
}

LL stk[maxn], tp, tmpa, tmpb;
bool better(const int &a, const int &b) {
	tmpa = dp[e[a].v][1] - dp[e[a].v][0] + e[a].w;
	tmpb = dp[e[b].v][1] - dp[e[b].v][0] + e[b].w;
	return tmpa == tmpb ? 
			((blk[e[a].v][1] - blk[e[a].v][0]) < 
			(blk[e[b].v][1] - blk[e[b].v][0])) : tmpa > tmpb;
}

void ref(LL &dp, int &blk, LL ndp, int nblk) {
	if(dp == ndp) {
		if(blk < nblk)
			blk = nblk;
	} else {
		if(dp < ndp) {
			dp = ndp;
			blk = nblk;
		}
	}
}

void work(int u, int p, LL cost) {
	int v, btot = 0, bans = 0;
	LL ans = 0, sum = 0; tp = 0;
	for(register int i = head[u]; i; i = e[i].next) {
		v = e[i].v;
		if(v == p) continue;
		sum += dp[v][0];
		stk[++tp] = i, btot += blk[v][0];
	}
	sort(stk + 1, stk + tp + 1, better);
	dp[u][0] = sum;
	blk[u][0] = btot;
	dp[u][1] = sum - cost;
	blk[u][1] = btot + 1;
	v = stk[1];
	ref(dp[u][1], blk[u][1], sum + e[v].w - dp[e[v].v][0] + dp[e[v].v][1], 
				btot - blk[e[v].v][0] + blk[e[v].v][1]);
	if(tp > 1) {
		ans = sum, v = stk[1], bans = btot;
		ans += e[v].w - dp[e[v].v][0] + dp[e[v].v][1];
		bans += blk[e[v].v][1] - blk[e[v].v][0];
		v = stk[2];
		ans += e[v].w - dp[e[v].v][0] + dp[e[v].v][1];
		bans += blk[e[v].v][1] - blk[e[v].v][0];
		ans += cost, --bans;
		ref(dp[u][0], blk[u][0], ans, bans);
	}
	ref(dp[u][0], blk[u][0], dp[u][1], blk[u][1]);
}

int DP(int u, int p, LL cost) {
	int leaf = 1;
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		DP(v, u, cost), leaf = 0;
	}
	if(leaf) {
		dp[u][0] = 0;
		dp[u][1] = -cost;
		blk[u][1] = 1;
		ref(dp[u][0], blk[u][0], dp[u][1], blk[u][1]);
	} else work(u, p, cost);
}

void init(int n) {
	for(register int i = 1; i <= n; ++i)
		dp[i][0] = dp[i][1] = -inf, blk[i][0] = blk[i][1] = 0;
}

int check(LL x) {
	init(n);
	DP(1, 0, x);
	return blk[1][0] >= k + 1;
}

LL solve(LL l, LL r) {
	while(l < r - 1) {
		LL mid = l + r >> 1;
		if(check(mid)) l = mid;
		else r = mid;
	}
	return l;
}

int main() {
	//freopen("lct20.in", "r", stdin);
	scanf("%d%d", &n, &k);
	for(register int i = 1; i < n; ++i)
		scanf("%d%d%d", &u, &v, &w), adde(u, v, w), adde(v, u, w);
	LL best = solve(-1ll*1e12, 1ll*1e12);
	check(best);
	printf("%lld", dp[1][0] + (k + 1) * best);
	return 0;
} 
```

Rockdu's Blog

导航

最近发表

大佬们的友链