#include using namespace std; #define REP(i,a,b) for(i=a;i void sort(int N, T1 a[], T2 b[], void *mem){ int i; pair *r=(pair*)mem; rep(i,N) r[i].first = a[i], r[i].second = b[i]; sort(r,r+N); rep(i,N) a[i] = r[i].first, b[i] = r[i].second; } template void unique(T arr[], int &sz){ int i, k=0; sort(arr,arr+sz); rep(i,sz){ if(!k||arr[k-1]!=arr[i]) arr[k++]=arr[i]; } sz=k; } char memarr[127000000]; void *gmem = memarr, *mem; vector edge[100000], cost[100000]; int es[100000]; int T, sumN; int N, L, R; int A[100000], B[100000], C[100000]; int Carr[100000]; int X, Y, Z; int st[100000], sts, now[100000], cnt, ind[100000], indd[100000]; int dp[55], val[55]; void getvaldfs(int n, int bef, int all, int ok){ int i, k; if(all > R) return; val[all] = max(val[all], ok); rep(i,es[n]){ k = edge[n][i]; if(k==bef || now[k]!=cnt) continue; getvaldfs(k, n, all+1, ok+(cost[n][i]<=Z?1:0)); } } void getinddfs(int n, int bef, int d){ int i, k; ind[n] = d; rep(i,es[n]){ k = edge[n][i]; if(k==bef || now[k]!=cnt) continue; getinddfs(k, n, d); } } int downdist[100000], updist[100000], fdist[100000]; void dfs1(int n, int bef){ int i, k; downdist[n] = 0; rep(i,es[n]){ k = edge[n][i]; if(k==bef || now[k]!=cnt) continue; dfs1(k, n); downdist[n] = max(downdist[n], downdist[k] + 1); } } void dfs2(int n, int bef, int up){ int i, k; int mx1=-1, mx2=-1; updist[n] = up; rep(i,es[n]){ k = edge[n][i]; if(k==bef || now[k]!=cnt) continue; if(mx1==-1){ mx1 = k; continue; } if(mx2==-1 || downdist[mx2] < downdist[k]) mx2 = k; if(downdist[mx1] < downdist[mx2]) swap(mx1, mx2); } rep(i,es[n]){ k = edge[n][i]; if(k==bef || now[k]!=cnt) continue; if(k==mx1) dfs2(k, n, max(up+1, mx2>=0?downdist[mx2]+2:-1)); else dfs2(k, n, max(up+1, downdist[mx1]+2)); } } int *list_st[1000000], list_sts[1000000], list_root[1000000], st_size; int ng[1000000], ok[1000000]; void gen_list(int st[], int sts){ int i, j, k, d; int root; if(sts<=L) return; cnt++; rep(i,sts) now[st[i]] = cnt; root = st[0]; dfs1(root, -1); dfs2(root, -1, 0); rep(i,sts) downdist[st[i]] = max(downdist[st[i]], updist[st[i]]); rep(i,sts) if(downdist[root] > downdist[st[i]]) root = st[i]; if(downdist[root]*2 < L) return; list_st[st_size] = (int*)mem; rep(i,sts) list_st[st_size][i] = st[i]; list_sts[st_size] = sts; list_root[st_size] = root; mem = list_st[st_size] + sts; st_size++; ind[root] = -1; d = 0; rep(i,es[root]){ k = edge[root][i]; if(now[k] != cnt) continue; getinddfs(k, root, d++); } rep(i,sts) indd[i] = ind[st[i]]; sort(sts, indd, st, mem); REP(i,1,sts){ j = i; while(j+1=0) rep(b,R+1) if(dp[b]>=0){ if(a+bR) break; if(val[a]+dp[b] > (a+b)/2) return 1; } rep(j,R+1) dp[j] = max(dp[j], val[j]); } return 0; } int main(){ int i, k, cs, z; scanf("%d",&T); while(T--){ mem = gmem; scanf("%d%d%d",&N,&L,&R); rep(i,N-1){ scanf("%d%d%d",A+i,B+i,C+i); A[i]--; B[i]--; } rep(i,N) edge[i].clear(); rep(i,N) cost[i].clear(); rep(i,N-1){ edge[A[i]].push_back(B[i]); cost[A[i]].push_back(C[i]); edge[B[i]].push_back(A[i]); cost[B[i]].push_back(C[i]); } rep(i,N) es[i] = edge[i].size(); cs = N-1; rep(i,N-1) Carr[i] = C[i]; unique(Carr, cs); R = min(2*L, R); st_size = 0; sts = 0; rep(i,N) st[sts++] = i; gen_list(st, sts); rep(i,st_size) ok[i] = 1000000000; rep(i,st_size) ng[i] = -1; X = 0; Y = cs; while(X < Y){ z = (X+Y) / 2; Z = Carr[z]; k = 0; rep(i,st_size){ if(ok[i] <= z) k = 1; else if(ng[i] >= z) k = 0; else{ k = solve(list_st[i], list_sts[i], list_root[i]); if(!k) ng[i] = z; else ok[i] = z; } if(k) break; } if(!k) X = z+1; else Y = z; } if(X==cs) X = -1; else X = Carr[X]; printf("%d\n",X); } return 0; }