Description：

给出一棵树，边有边权，求树上的前 $k$ 小路径。

$1\leqslant n\leqslant 10^6$

Solution：

思考一下如果我们有了一个堆，这个堆里有树上的所有路径，那么我们只要 $pop\ k$ 次就行了。

其实是可以做到的，设 $f[i]$ 表示 $i$ 这个点为最高点的直上直下的一条链的堆，这个显然可以用可并堆合并儿子节点打标记来计算， $g[i]$ 表示从 $i$ 的父亲到达 $i$ 的路径的堆，这个可以用可并堆合并 $g[fa[i]]$ 还有子树的前缀 $f$ 堆和后缀 $f$ 堆再打标记来计算，注意必须可持久化，最后把每个点的 $f$ 和 $g$ 都合并在一起就得到了一个包含所有路径的堆。

但是这题空间不够所以不能这样做。

有一个东西叫做点分治序，具体来说就是把点分治时经过的序列记录下来，长度为 $n\log n$ ，这个序列的一个重要的性质是对于当前这个分治重心，假设我们已经知道了从他出发的一条链，我们想找一个从他出发的另一条链，那么会发现这条链的端点在点分序上是一段连续的区间，然后问题就变成了每个 $a$ 可以选的范围都是连续的一段 $b$ ，一个 $pair(a,b)$ 的权值是 $a$ 和 $b$ 的权值之和，求第 $K$ 大，类似超级钢琴，用一个 $ST$ 表然后一个堆就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int v)

{

	e[++edgenum] = (edge){b,lin[a],v};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],v};lin[b] = edgenum;

	return;

}

#define MAXL (MAXN * 20)

int dfn[MAXL],mid[MAXL],len[MAXL],lef[MAXL],rig[MAXL],tot = 0;//µã·ÖÐò

int st[MAXL][26];

#define INF 0x3f3f3f3f

int root,s,siz[MAXN],d[MAXN];

bool vis[MAXN];

void getroot(int k,int fa)

{

	siz[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		getroot(e[i].to,k);

		siz[k] += siz[e[i].to];

		d[k] = max(d[k],siz[e[i].to]);

	}

	d[k] = max(d[k],s - siz[k]);

	if(d[k] < d[root])root = k;

	return;

}

void getd(int k,int fa,int d)

{

	dfn[++tot] = k;mid[tot] = mid[tot - 1];len[tot] = d;

	lef[tot] = lef[tot - 1];

	rig[tot] = (rig[tot] ? rig[tot] : rig[tot - 1]);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to] || e[i].to == fa)continue;

		getd(e[i].to,k,d + e[i].v);

	}

	return;

}

void divide(int rt)

{

	vis[rt] = true;

	dfn[++tot] = rt;mid[tot] = rt;

	lef[tot] = tot;rig[tot] = tot - 1;

	for(int i = lin[rt];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		rig[tot + 1] = tot;

		getd(e[i].to,0,e[i].v);

	}

	for(int i = lin[rt];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		root = 0;s = siz[e[i].to];

		getroot(e[i].to,0);

		divide(root);

	}

}

int mymax(int a,int b)

{

	return (len[a] > len[b] ? a : b);

}

int lg[MAXL];

int query(int l,int r)

{

	int len = lg[r - l + 1];

	return mymax(st[l][len],st[r - (1 << len) + 1][len]);

}

struct node

{

	int s,l,r,p,v;

	friend bool operator < (const node& a,const node& b)

	{

		return a.v < b.v;

	}

};

priority_queue<node> q;

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	s = n;root = 0;d[0] = INF;

	getroot(1,0);

	divide(root);

	for(int i = 1;i <= tot;++i)st[i][0] = i;

	for(int i = 2;i <= tot;++i)lg[i] = lg[i >> 1] + 1;

	for(int k = 1,l = 1;k <= 25;++k,l = l << 1)

		for(int i = 1;i <= tot - l * 2 + 1;++i)

			st[i][k] = mymax(st[i][k - 1],st[i + l][k - 1]);

	int sum = 0;

	for(int i = 1;i <= tot;++i)sum += rig[i] - lef[i] + 1;

	for(int i = 1;i <= tot;++i)

	{

		if(lef[i] > rig[i])continue;

		q.push((node){i,lef[i],rig[i],query(lef[i],rig[i]),len[query(lef[i],rig[i])] + len[i]});

	}

	for(int i = 1;i <= m;++i)

	{

		node k = q.top();q.pop();

		printf("%d\n",k.v);

		if(k.l < k.p)

		{

			q.push((node){k.s,k.l,k.p - 1,query(k.l,k.p - 1),len[query(k.l,k.p - 1)] + len[k.s]});

		}

		if(k.p < k.r)

		{

			q.push((node){k.s,k.p + 1,k.r,query(k.p + 1,k.r),len[query(k.p + 1,k.r)] + len[k.s]});

		}

	}

	return 0;

}