引入

题目地址

题目大意：给一棵 NN 个点、有边权的树，求最小的不小于k的一条树上路径的长度。

我的第一想法肯定是把每个节点的的信息不断像上传，同时还在这个节点的位置处理子树中到它和跨过它的路径的信息，但这样的复杂度是最坏 Θ(N2)\Theta(N^2) 的，只需要用一条链就可以轻松卡掉它。。。
看一眼数据范围，典型的要带一两个 loglog 那怎么办，就引出我们的主题了：

树上启发式合并（dsu on tree）

这玩意乍一看很玄学，因为启发式就显得它很难懂，也很高大上，但事实上你只需要感性理解一下，放轻松~

回忆一下重链剖分中，对于一棵树的一个节点，从根节点到它的轻边数是不超过 logNlog N 的[^1]，

那我们便可以考虑对所有轻边连接的子树中的节点暴力进行遍历；
而对于重边连接的子树的信息我们则选择保留而不是传到父亲后重新遍历。

这样一个节点总体上被遍历的次数便不会超过根节点到它的轻边数 logN+1logN+1 ，加 11 是因为到它自己更新信息时要遍历它自己

总时间复杂度便为 Θ(NlogN)\Theta(NlogN)

对于本题

说完了知识点总得回归到题目吧，对于这道题我们可以先 Θ(N)\Theta(N) 求出每个节点到根节点的路径长度（即深度）、重儿子、子树大小、 dfs 序，

然后我们用 set 维护那个要传着用的值，也就是重儿子那一棵子树上所有节点到根路径的长度，根据每次新暴力加进来的节点到当前节点的长度，用 lower_bound ( ) 查询最有希望成为和这个长度加起来更新答案的值，并更新答案。

去除轻子树的影响时只需要在遍历完这棵子树后清空 set 即可

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,head[500005],cnt=1,a,b,c,d[500005],dfn[500005],r[500005],tot,hev[500005],size[500005],ans,dfnto[500005];
struct edge{
	ll to,next,w;
}e[1000005];
set<ll> s;
void make(ll u,ll v,ll w){
	e[cnt].to=v;
	e[cnt].next=head[u];
	e[cnt].w=w;
	head[u]=cnt++;
}
void dfs1(ll x,ll fa,ll depth){
	d[x]=depth;
	dfn[x]=++tot;
	dfnto[tot]=x;
	ll biggest=0;
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to==fa)continue;
		dfs1(e[i].to,x,depth+e[i].w);
		size[x]+=size[e[i].to]+1;
		if(size[e[i].to]+1>biggest)
		biggest=size[e[i].to]+1,hev[x]=e[i].to;
	}
	r[x]=tot;
}
void in(ll x,ll cut){
	auto it=s.lower_bound(k-x+2*cut);
	if(it!=s.end()){
		if(x+*it-2*cut>=k)
		ans=min(ans,x+*it-2*cut);
	}
	else if(x-cut>=k)ans=min(ans,x-cut);
	s.insert(x);
}
void dfs2(ll x,ll fa,ll add){
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to!=hev[x]&&e[i].to!=fa)dfs2(e[i].to,x,0);
	}
	if(hev[x])dfs2(hev[x],x,1);
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to!=fa&&e[i].to!=hev[x]){
			for(int j=dfn[e[i].to];j<=r[e[i].to];j++){
				in(d[dfnto[j]],d[x]);
			}
		}
	}
	in(d[x],d[x]);
	if(add==0){
		s.clear();
	}
}
int main(){
	freopen("tree.in","r",stdin); 
	freopen("tree.out","w",stdout); 
	cin>>n>>k;
	for(int i=1;i<n;i++){
		cin>>a>>b>>c;
		make(b,a,c);
		make(a,b,c);
	}
	ans=1e18;
	dfs1(1,0,0);
	dfs2(1,0,0);
	if(ans==1e18)
	cout<<-1;
	else
	cout<<ans;
	return 0;
}

[^1]: 证明：设 xx 为根节点到该节点的轻边数， yy 为该节点的子树大小，那么因为轻边连接的子树最大不大于它的父节点的子树大小的一半，所以有 y<=N2xy<=\cfrac{N}{2^x} ，所以x<logNx<logN