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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=6e4+10;
const int NM=8e5+10;
const double eps=1e-8;
#define ll long long
const int inf=1e9;
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n;ll m;
int key,rt,maxx[MAXN],sz[MAXN],base;
bool vis[MAXN];
int tot,pos[NM][18],dp[NM];
int L[NM],R[NM],ma[NM];
void get_root(int x,int pre){
maxx[x]=0;sz[x]=1;
link(x){
if(j->t==pre||vis[j->t])continue;
get_root(j->t,x);
sz[x]+=sz[j->t];maxx[x]=max(maxx[x],sz[j->t]);
}
maxx[x]=max(maxx[x],base-sz[x]);
if(key>maxx[x])key=maxx[x],rt=x;
}
int dis[MAXN];
int l,r;
void dfs(int x,int pre){
tot++;
pos[tot][0]=tot;
dp[tot]=dis[x];L[tot]=l;R[tot]=r;
link(x){
if(vis[j->t]||j->t==pre)continue;
dis[j->t]=dis[x]+j->v;
dfs(j->t,x);
}
}
void solve(int x){
vis[x]=1;tot++;
pos[tot][0]=tot;dp[tot]=0;L[tot]=tot;R[tot]=tot;
l=tot;r=tot;
link(x){
if(vis[j->t])continue;
dis[j->t]=j->v;dfs(j->t,x);
r=tot;
}
link(x){
if(vis[j->t])continue;
key=inf;base=sz[j->t];get_root(j->t,0);
solve(rt);
}
}
void St(){
inc(i,2,tot)ma[i]=ma[i/2]+1;
inc(j,1,17){
for(int i=1;i+(1<<j)<=tot+1;i++){
if(dp[pos[i][j-1]]>=dp[pos[i+(1<<(j-1))][j-1]])pos[i][j]=pos[i][j-1];
else pos[i][j]=pos[i+(1<<(j-1))][j-1];
}
}
}
int rmq(int l,int r){
if(l>r)return 0;
int k=ma[r-l+1];
if(dp[pos[l][k]]>=dp[pos[r-(1<<k)+1][k]])return pos[l][k];
else return pos[r-(1<<k)+1][k];
}
typedef struct node{
int l,r,pos,id,k;
friend bool operator<(node aa,node bb){return aa.k<bb.k;}
}node;
priority_queue<node>que;
int main(){
n=read();m=read();
int x,y,z;tot=0;
m=min(m,1ll*n*(n-1)/2);
inc(i,2,n)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
base=n;key=inf;get_root(1,0);
solve(rt);
St();
inc(i,1,tot){
int t=rmq(L[i],R[i]);
que.push((node){L[i],R[i],t,i,dp[t]+dp[i]});
}
inc(i,1,m){
printf("%d\n",(que.top()).k);
node p=que.top();que.pop();
int t1=rmq(p.l,p.pos-1);
int t2=rmq(p.pos+1,p.r);
if(t1)que.push((node){p.l,p.pos-1,t1,p.id,dp[p.id]+dp[t1]});
if(t2)que.push((node){p.pos+1,p.r,t2,p.id,dp[p.id]+dp[t2]});
}
return 0;
}
|