第三道点分治。
首先找到黄学长的题解，他叫我参考XXX的题解，但已经没有了，然后找到另一个博客的简略题解，没看懂，最后看了一个晚上黄学长代码，写出来然后，写暴力都拍了小数据，但居然超时，。。。。然后改了一下存图方式，还是T，读入优化，还是T，最后把BFS找重心改成DFS找重心后才过的（因为DFS只遍历一遍，但BFS要多遍历几遍）。
————————————————————以上是废话————————————————————————
题目：给定一个边带权的无根树，求长度排名为前m的路径的长度。
首先，肯定不能求出所有路径来排序，因为n很大。但我们要求前m大的路径，容易想到，我们先求出极大路径，求出最大，删掉它，然后再加上新产生的极大路径，但我们怎么定义“极大路径”呢，是长度不能再延伸的路径吗，可以发现这样选择，求新产生的极大路径会出现问题。
那这道题是怎么做的呢？在点分治时，每一个重心会对应很多棵子树，先对当前重心代表的那一棵树进行一次DFS，幷保存每个点的DFS序，以及DFS序中每个位置对应点到当前重心的距离，并且我们为每个点保存一个DFS序的区间，该区间包含根和包含它的子树的左边的子树（不包含它所在的子树），这样元素(lf,rg,x)代表dfs序上第x个点与区间[lf,rg]上代表的点的路径，即它代表一些路径而不是一条。并且可以证明每一条路径属于且仅属于其中一个元素。
每个元素代表的路径中存在最长的路径，以该路径的长度为关键字将元素放进堆中，每次找到后，将那个元素分成两个。。。。。。。
。。。。。。。。。。
/**************************************************************
Problem: 3784
User: idy002
Language: C++
Result: Accepted
Time:6940 ms
Memory:208820 kb
****************************************************************/ #include <cstdio>
#include <cctype>
#include <vector>
#include <queue>
#define max(a,b) ((a)>(b)?(a):(b))
#define N 50010
#define S 2000010
using namespace std; void gn( int &a ) {
char ch;
ch = getchar();
while( ch<''||ch>'' ) ch=getchar();
a = ;
while( ''<=ch&&ch<='' ) {
a = a*+ch-'';
ch = getchar();
}
} int n, m;
int head[N], dest[N+N], wght[N+N], next[N+N], ntot;
int vis[N], dis[N], siz[N], bac[N], fat[N], tot_siz, cur_root;
int qdis[S], qlf[S], qrg[S], clf, crg, ind;
int stm[S][], bin[], log[N];
int qu[N], bg, ed; struct Paths {
int lf, rg, mx, cur;
Paths( int lf, int rg, int mx, int cur ):lf(lf),rg(rg),mx(mx),cur(cur) {}
bool operator<( const Paths & b ) const {
return qdis[mx]+qdis[cur] < qdis[b.mx]+qdis[b.cur];
}
};
priority_queue<Paths> pq; void insert( int u, int v, int w ) {
ntot++;
next[ntot] = head[u];
wght[ntot] = w;
dest[ntot] = v;
head[u] = ntot;
}
void dfs_dis( int u ) {
ind++;
qdis[ind] = dis[u];
qlf[ind] = clf;
qrg[ind] = crg;
for( int t=head[u]; t; t=next[t] ) {
int v=dest[t], w=wght[t];
if( vis[v] || v==fat[u] ) continue;
dis[v] = dis[u]+w;
fat[v] = u;
dfs_dis( v );
}
} void dfs_root( int u ) {
siz[u] = ;
bac[u] = ;
for( int t=head[u]; t; t=next[t] ) {
int v=dest[t];
if( vis[v] || v==fat[u] ) continue;
fat[v] = u;
dfs_root( v );
siz[u] += siz[v];
if( siz[v]>bac[u] ) bac[u]=siz[v];
}
if( bac[u]<tot_siz-siz[u] ) bac[u] = tot_siz-siz[u];
if( bac[cur_root]>bac[u] ) cur_root=u;
}
void build_vdcp( int rt ) {
tot_siz = siz[rt];
cur_root = ;
fat[rt] = rt;
dfs_root( rt );
rt = cur_root;
/* find the core of the block that not cross the vertex of visited */
/*
qu[bg=ed=1] = rt;
fat[rt] = rt;
siz[rt] = bac[rt] = 0;
while( ed>=bg ) {
int u=qu[bg++];
for( int t=head[u]; t; t=next[t] ) {
int v=dest[t];
if( vis[v] || v==fat[u] ) continue;
qu[++ed] = v;
fat[v] = u;
siz[u] = bac[u] = 0;
}
}
for( int i=ed; i>=1; i-- ) {
int u=qu[i];
int p=fat[u];
siz[u]++;
siz[p] += siz[u];
if( bac[p]<siz[u] ) bac[p]=siz[u];
}
for( int i=ed; i>=1; i-- ) {
int u=qu[i];
if( bac[u]<siz[rt]-siz[u] ) bac[u]=siz[rt]-siz[u];
}
for( int i=ed; i>=1; i-- ) {
int u=qu[i];
if( bac[rt]>bac[u] ) rt=u;
}
*/
/* get the info of cur core */
ind++;
qdis[ind] = ;
qlf[ind] = qrg[ind] = ;
clf = crg = ind;
vis[rt] = true;
for( int t=head[rt]; t; t=next[t] ) {
int u=dest[t], w=wght[t];
if( vis[u] ) continue;
fat[u] = rt;
dis[u] = w;
fat[u] = u;
dfs_dis( u );
crg = ind;
}
for( int t=head[rt]; t; t=next[t] ) {
int u=dest[t];
if( vis[u] ) continue;
build_vdcp( u );
}
}
void build_stable() {
bin[] = ;
for( int i=; i<; i++ ) bin[i]=bin[i-]<<;
log[] = -;
for( int i=; i<=n; i++ ) log[i]=log[i>>]+;
for( int i=; i<=ind; i++ ) stm[i][] = i;
for( int p=; p<=log[n]; p++ )
for( int i=; i<=ind-bin[p]+; i++ ) {
int a = stm[i][p-];
int b = stm[i+bin[p-]][p-];
stm[i][p] = qdis[a]>qdis[b] ? a : b;
}
}
int rmq( int lf, int rg ) {
int len = rg-lf+;
int p = log[len];
int a = stm[lf][p];
int b = stm[rg-bin[p]+][p];
return qdis[a]>qdis[b] ? a : b;
}
int main() {
gn(n), gn(m);
for( int i=,u,v,w; i<n; i++ ) {
gn(u), gn(v), gn(w);
insert( u, v, w );
insert( v, u, w );
}
bac[] = n, siz[] = n;
build_vdcp( );
build_stable();
for( int i=; i<=ind; i++ )
if( qlf[i] ) pq.push( Paths(qlf[i],qrg[i],rmq(qlf[i],qrg[i]),i) );
for( int i=; i<=m; i++ ) {
Paths pth = pq.top();
pq.pop();
printf( "%d\n", qdis[pth.mx]+qdis[pth.cur] );
if( pth.lf<=pth.mx- ) pq.push( Paths(pth.lf,pth.mx-,rmq(pth.lf,pth.mx-),pth.cur) );
if( pth.rg>=pth.mx+ ) pq.push( Paths(pth.mx+,pth.rg,rmq(pth.mx+,pth.rg),pth.cur) );
}
}