我直接来讲在线好了
这是一个很巧妙的方法，把边作为一个点
做一遍最小生成树，当加如一条边时，我们把这条边两点x,y的并查集的根i,j的父亲都设为这条边代表的点k，由k向i，j连边
这样我们就构建出一棵树，这棵树的叶子都是原来节点
且每棵子树都是在子树根所代表的边的限制下的最小连通块
这样我们就可以通过dfs序（只用对叶子标号）+主席树来维护k大了并通过倍增找到限制
这两题都是一副卡pascal过不了的样子……QAQ
另外网上的一些标称（bzoj3551）似乎没有考虑一个点没有边可走，但询问k=1的情况，可以加数据cha
1 type node=record 2 po,next:longint; 3 end; 4 way=record 5 x,y,z:longint; 6 end; 7 point=record 8 l,r,s:longint; 9 end; 10 11 var e:array[0..400010] of node; 12 w:array[0..500010] of way; 13 v:array[0..400010] of boolean; 14 anc:array[0..200010,0..20] of longint; 15 d,l,r,p,fa,c,a,b,h:array[0..200010] of longint; 16 tree:array[0..200010*20] of point; 17 num,j,s,size,i,len,t,n,m,q,x,y,ans,k:longint; 18 19 function min(a,b:longint):longint; 20 begin 21 if a>b then exit(b) else exit(a); 22 end; 23 24 function max(a,b:longint):longint; 25 begin 26 if a>b then exit(a) else exit(b); 27 end; 28 29 function getf(x:longint):longint; 30 begin 31 if fa[x]<>x then fa[x]:=getf(fa[x]); 32 exit(fa[x]); 33 end; 34 35 procedure swap(var a,b:longint); 36 var c:longint; 37 begin 38 c:=a; 39 a:=b; 40 b:=c; 41 end; 42 43 procedure sort(l,r:longint); 44 var i,j,x:longint; 45 begin 46 i:=l; 47 j:=r; 48 x:=a[(l+r) shr 1]; 49 repeat 50 while a[i]j; 60 if l j; 81 if l 0 do101 begin102 y:=e[i].po;103 anc[y,0]:=x;104 dfs(y);105 l[x]:=min(l[x],l[y]);106 r[x]:=max(r[x],r[y]);107 i:=e[i].next;108 end;109 end;110 111 function find(x,y:longint):longint;112 var i:longint;113 begin114 for i:=size downto 0 do115 if a[anc[x,i]]<=y then x:=anc[x,i];116 exit(x);117 end;118 119 function build(l,r:longint):longint;120 var m,q:longint;121 begin122 inc(t);123 q:=t;124 if l<>r then125 begin126 m:=(l+r) shr 1;127 tree[q].l:=build(l,m);128 tree[q].r:=build(m+1,r);129 end;130 exit(q);131 end;132 133 function add(l,r,last,x:longint):longint;134 var m,q:longint;135 begin136 inc(t);137 q:=t;138 if l=r then tree[q].s:=tree[last].s+1139 else begin140 m:=(l+r) shr 1;141 if x<=m then142 begin143 tree[q].r:=tree[last].r;144 tree[q].l:=add(l,m,tree[last].l,x);145 end146 else begin147 tree[q].l:=tree[last].l;148 tree[q].r:=add(m+1,r,tree[last].r,x);149 end;150 tree[q].s:=tree[tree[q].l].s+tree[tree[q].r].s;151 end;152 exit(q);153 end;154 155 function ask(l,r,x,y,k:longint):longint;156 var m,s:longint;157 begin158 if l=r then exit(c[l])159 else begin160 m:=(l+r) shr 1;161 s:=tree[tree[y].r].s-tree[tree[x].r].s;162 if s>=k then exit(ask(m+1,r,tree[x].r,tree[y].r,k))163 else exit(ask(l,m,tree[x].l,tree[y].l,k-s));164 end;165 end;166 167 procedure ins(x,y:longint);168 begin169 inc(len);170 e[len].po:=y;171 e[len].next:=p[x];172 p[x]:=len;173 end;174 175 begin176 readln(n,m,q);177 for i:=1 to n do178 begin179 read(d[i]);180 a[i]:=d[i];181 b[i]:=i;182 end;183 sort(1,n);184 s:=1;185 d[b[1]]:=1;186 c[1]:=a[1];187 for i:=2 to n do188 begin189 if a[i]<>a[i-1] then190 begin191 inc(s);192 c[s]:=a[i];193 end;194 d[b[i]]:=s;195 end;196 for i:=1 to 2*n do197 fa[i]:=i;198 for i:=1 to m do199 readln(w[i].x,w[i].y,w[i].z);200 201 qsort(1,m);202 t:=n;203 fillchar(a,sizeof(a),0);204 for i:=1 to m do205 begin206 x:=getf(w[i].x);207 y:=getf(w[i].y);208 if x<>y then209 begin210 inc(t);211 fa[x]:=t;212 fa[y]:=t;213 a[t]:=w[i].z;214 ins(t,x);215 ins(t,y);216 if t=2*n-1 then break;217 end;218 end;219 220 a[0]:=2147483647;221 len:=t;222 for i:=1 to len do223 if not v[i] then dfs(getf(i));224 size:=trunc(ln(len)/ln(2)+0.1);225 for j:=1 to size do226 for i:=1 to len do227 begin228 x:=anc[i,j-1];229 anc[i,j]:=anc[x,j-1];230 end;231 t:=0;232 h[0]:=build(1,s);233 for i:=1 to num do234 h[i]:=add(1,s,h[i-1],d[b[i]]);235 ans:=-1;236 for i:=1 to q do237 begin238 readln(x,y,k);239 { if ans<>-1 then240 begin241 x:=x xor ans;242 y:=y xor ans;243 k:=k xor ans;244 end; }245 x:=find(x,y);246 if x<=n then247 begin248 if k=1 then ans:=c[d[x]]249 else ans:=-1;250 end251 else if tree[h[r[x]]].s-tree[h[l[x]-1]].s