【题解】[八省联考2018]林克卡特树

Posted on Edited on

简要题意

给定一棵树, 定义路径的权值为所经过的边的权值之和.

现在可以删掉 $k$ 条边, 并再连接 $k$ 条边权为 $0$ 的边, 得到一棵新的树.

最大化能得到的路径权值.

$1 \leqslant n \leqslant 3 \times 10^5,|v_i| \leqslant 10^6$ .

题解

断掉 $k$ 条边, 相当于变成 $k+1$ 个连通块, 选每个连通块的直径, 把他们用 $0$ 的边连起来, 就可以得到最大值.

所以原题意相当于, 选 $k+1$ 条树上不相交的简单路径, 求最大值, 显然这是个上凸的函数, 考虑 $wqs$ 二分.

尝试设计 $wqs$ 二分里面的 $dp$ , 这里顺便总结一个记录路径延伸情况的常见套路.

由于一个节点的度数不会超过 $2$ , 因此设 $f_{i,j}$ 其中 $j \in [0,2]$ , 表示在以 $i$ 为根的子树中, 节点 $i$ 的度数为 $j$ 时的答案, 且 $j=1$ 时与 $i$ 相连的链不计入链的总数.

另外记录当前 $dp$ 值下链的条数的最大值方便判断 $wqs$ 二分截得的点的横坐标. 记 $g_i = \max\{f_{i,0},f_{i,1}-k,f_{i,2}\}$ , 设当其合并 $i$ 与其儿子 $j$ , 有转移方程,

不难发现 $g_i$ 表示以 $i$ 为根的子树中, 与 $i$ 的父亲不连边时的答案, 而 $f_{i,1}-k$ 相当于在 $i$ 处直接把链给掐了, 因此 $g_1$ 即为所求.

注意转移顺序.

时间复杂段线性对数.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/************************************************
*Author        :  demonlover
*Created Time  :  2022.02.04.14:28
*Problem       :  luogu4383
************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << "\n"
template <typename T>
inline bool read(T &x) {
	int f = 1,c = getchar();x = 0;
	while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
	while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
	return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
	return read(x) && read(args...);
}

namespace run {
	const int maxn = 3e5+10;
	struct Edge {int nxt,to,w;}edge[maxn<<1];
	int begn[maxn],e;
	inline void add(int x,int y,int z) {
		edge[++e] = (Edge){begn[x],y,z};begn[x] = e;
		return;
	}
	struct DP {
		ll f;
		int num;
		DP (ll F = 0,int Num = 0) {f = F;num = Num;}
		bool operator < (const DP &rhs) const {
			return (f ^ rhs.f) ? f < rhs.f : num < rhs.num;
		}
	}I,f[maxn][3];
	DP operator + (DP x,DP y) {return DP(x.f+y.f,x.num+y.num);}
	inline void dfs(int x,int fa) {
		f[x][0] = f[x][1] = DP(0,0);f[x][2] = I;
		for (int i = begn[x];i;i = edge[i].nxt) {
			int y = edge[i].to;
			if (y ^ fa) {
				dfs(y,x);
				DP tmp = DP(edge[i].w,0);
				f[x][2] = max(f[x][2],max(f[x][1]+tmp+f[y][1]+I,f[x][2]+f[y][0]));
				f[x][1] = max(f[x][1],max(f[x][0]+f[y][1]+tmp,f[x][1]+f[y][0]));
				f[x][0] = max(f[x][0],f[x][0]+f[y][0]);
			}
		}
		f[x][0] = max(f[x][0],max(f[x][1]+I,f[x][2]));
		return;
	}
	int n,K;
	ll ans;
	inline bool main() {
		read(n,K);++K;
		for (int i = 1,x,y,z;i < n;++i)read(x,y,z),add(x,y,z),add(y,x,z);
		int l = -1e8,r = 1e8;
		while (l < r) {
			int mid = ((l+r)>>1)+1;
			I = DP(-mid,1);
			dfs(1,0);
			if (f[1][0].num >= K)l = mid,ans = f[1][0].f+1ll*mid*K;
			else r = mid-1;
			if (f[1][0].num == K)break;
		}
		printf("%lld\n",ans);
		cerr<<1.0*clock()/CLOCKS_PER_SEC<<"\n";
		return 0;
	}
}

#define demonlover
int main() {
#ifdef demonlover
	freopen("luogu4383.in","r",stdin);
	freopen("luogu4383.out","w",stdout);
#endif
	return run :: main();
}