双倍经验题
像这种方案太多不能全部求出来但求前k大一般有这样一个思路
将所有方案无重复不漏的分为若干类，每个类的元素满足单调性，然后我们用堆维护就行了！
对于这道题，可以想到用树的分治来处理路径，当处理根为x时
我们处理当前的子树每个点i和之前的子树上的组成的路径，
我们完全可以把访问顺序状态记录成一条链（状态是nlogn规模不会爆）
当前子树的每个点i在链上都有一段连续的可选区间，这个区间的点和i构成一条过根x的路径
这样链上的每个点就代表了一类路径
很明显，我们就可以noi超级钢琴的做法来解决，st表预处理+堆维护
1 type way=record 2 po,num,next:longint; 3 end; 4 node=record 5 l,r,s,t:longint; 6 end; 7 8 var e:array[0..100010] of way; 9 h:array[0..1000010] of node; 10 w:array[0..1000010,0..20] of longint; 11 d:array[0..20] of longint; 12 a:array[0..1000010] of longint; 13 q:array[0..1000010,0..1] of longint; 14 f,p,s:array[0..50010] of longint; 15 v:array[0..50010] of boolean; 16 l,r,root,len,t,tot,i,n,k,x,y,z,j:longint; 17 m:node; 18 19 function max(a,b:longint):longint; 20 begin 21 if a>b then exit(a) else exit(b); 22 end; 23 24 function mx(x,y:longint):longint; 25 begin 26 if a[x]>a[y] then exit(x) else exit(y); 27 end; 28 29 function ask(x,y:longint):longint; 30 var k:longint; 31 begin 32 k:=trunc(ln(y-x+1)/ln(2)); 33 exit(mx(w[x,k],w[y-d[k]+1,k])); 34 end; 35 36 procedure swap(var a,b:node); 37 var c:node; 38 begin 39 c:=a; 40 a:=b; 41 b:=c; 42 end; 43 44 procedure add(x,y,z:longint); 45 begin 46 inc(len); 47 e[len].po:=y; 48 e[len].num:=z; 49 e[len].next:=p[x]; 50 p[x]:=len; 51 end; 52 53 procedure up(i:longint); 54 var j:longint; 55 begin 56 j:=i shr 1; 57 while j>0 do 58 begin 59 if a[h[j].s]+a[h[j].t]<a[h[i].s]+a[h[i].t] then 60 begin 61 swap(h[i],h[j]); 62 i:=j; 63 j:=j shr 1; 64 end 65 else break; 66 end; 67 end; 68 69 procedure sift(i:longint); 70 var j:longint; 71 begin 72 j:=i shl 1; 73 while j<=t do 74 begin 75 if (j<t) and (a[h[j+1].s]+a[h[j+1].t]>a[h[j].s]+a[h[j].t]) then inc(j); 76 if a[h[j].s]+a[h[j].t]>a[h[i].s]+a[h[i].t] then 77 begin 78 swap(h[i],h[j]); 79 i:=j; 80 j:=j shl 1; 81 end 82 else break; 83 end; 84 end; 85 86 procedure getroot(x,fa:longint); 87 var i,y:longint; 88 begin 89 s[x]:=1; 90 f[x]:=0; 91 i:=p[x]; 92 while i<>0 do 93 begin 94 y:=e[i].po; 95 if (y<>fa) and not v[y] then 96 begin 97 getroot(y,x); 98 s[x]:=s[x]+s[y]; 99 f[x]:=max(f[x],s[y]); 100 end; 101 i:=e[i].next; 102 end; 103 f[x]:=max(f[x],tot-s[x]); 104 if f[x]<f[root] then root:=x; 105 end; 106 107 procedure get(x,fa,len:longint); 108 var i,y:longint; 109 begin 110 inc(t); 111 a[t]:=len; 112 q[t,0]:=l; q[t,1]:=r; 113 i:=p[x]; 114 while i<>0 do 115 begin 116 y:=e[i].po; 117 if (y<>fa) and not v[y] then get(y,x,len+e[i].num); 118 i:=e[i].next; 119 end; 120 end; 121 122 procedure work(x:longint); 123 var i,y:longint; 124 begin 125 v[x]:=true; 126 i:=p[x]; 127 inc(t); 128 l:=t; 129 r:=t; 130 q[t,0]:=l; q[t,1]:=r; 131 while i<>0 do 132 begin 133 y:=e[i].po; 134 if not v[y] then 135 begin 136 r:=t; 137 get(y,x,e[i].num); 138 end; 139 i:=e[i].next; 140 end; 141 i:=p[x]; 142 while i<>0 do 143 begin 144 y:=e[i].po; 145 if not v[y] then 146 begin 147 root:=0; 148 tot:=s[y]; 149 getroot(y,0); 150 work(root); 151 end; 152 i:=e[i].next; 153 end; 154 end; 155 156 begin 157 readln(n,k); 158 for i:=1 to n-1 do 159 begin 160 readln(x,y,z); 161 add(x,y,z); 162 add(y,x,z); 163 end; 164 f[0]:=2147483647; 165 tot:=n; 166 getroot(1,0); 167 work(root); 168 tot:=trunc(ln(t)/ln(2)); 169 d[0]:=1; 170 for i:=1 to tot do 171 d[i]:=d[i-1]*2; 172 173 for i:=1 to t do 174 w[i,0]:=i; 175 for j:=1 to tot do 176 for i:=1 to t do 177 if i+d[j]-1<=t then 178 w[i,j]:=mx(w[i,j-1],w[i+d[j-1],j-1]) 179 else break; 180 181 tot:=t; t:=0; 182 for i:=1 to tot do 183 begin 184 inc(t); 185 with h[t] do 186 begin 187 l:=q[i,0]; r:=q[i,1]; 188 s:=i; 189 t:=ask(l,r); 190 end; 191 up(t); 192 end; 193 for i:=1 to k do 194 begin 195 writeln(a[h[1].s]+a[h[1].t]); 196 swap(h[1],h[t]); 197 m:=h[t]; 198 dec(t); 199 sift(1); 200 if m.t>m.l then 201 begin 202 inc(t); 203 with h[t] do 204 begin 205 l:=m.l; r:=m.t-1; 206 s:=m.s; 207 t:=ask(l,r); 208 end; 209 up(t); 210 end; 211 if m.t<m.r then 212 begin 213 inc(t); 214 with h[t] do 215 begin 216 l:=m.t+1; r:=m.r; 217 s:=m.s; 218 t:=ask(l,r); 219 end; 220 up(t); 221 end; 222 end; 223 end.