//#include "testlib.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int n, L, R; int dp[111][111111]; int dq[111111]; int last[111111]; int p[111111]; vector > g[111111]; bool found; bool used[111111]; int st[111111]; bool can(int med) { // uses non-recursive dfs found = 0; int top = 1; st[top] = 1; // assume that root of the tree will be '1' p[1] = 0; memset(used, 0, sizeof used); memset(last, -1, sizeof last); int lj, rj, f, l, edge, v, flag; while (top != 0) { // start dfs v = st[top]; used[v] = 1; flag = 0; for(int i = last[v]+1; i < g[v].size(); ++i) if (!used[g[v][i].first]) { // if there is unvisited son, we should process it p[g[v][i].first] = v; last[v] = i; st[++top] = (g[v][i].first); flag = 1; break; } if (!flag) { // if we processed all sons of this node top--; for(int i = 0; i <= R; ++i) dp[i][v] = -1e9; dp[0][v] = 0; for(auto to : g[v]) { if (to.first == p[v]) continue; edge = to.second > med ? -1 : 1; //lj+1+1==L //rj+1+1==R lj = L - 2; rj = R - 2; f = 0, l = 0; dq[l] = (dp[rj][to.first] + edge); for(int i = rj-1; i >= lj; --i) { while (f <= l && dq[l] < dp[i][to.first] + edge) l--; dq[++l] = dp[i][to.first] + edge; } for(int i = 1; i <= R; ++i) { // j == L - i - 1 // j == R - i - 1 if (f <= l) if (dp[i][v] + dq[f] > 0) return 1; lj--; rj--; if (lj >= 0) { while (f <= l && dq[l] < dp[lj][to.first] + edge) l--; dq[++l] = dp[lj][to.first] + edge; } if (rj+1 >= 0) if (dq[f] == dp[rj+1][to.first] + edge) ++f; } for(int i = 1; i <= R; ++i) { dp[i][v] = max(dp[i][v], dp[i-1][to.first] + edge); if (i >= L && dp[i][v] > 0) return 1; } } } } return 0; } int main() { //ios::sync_with_stdio(0); int t; scanf("%d", &t); //cin >> t; while (t --> 0) { int a, b, c; scanf("%d %d %d", &n, &L, &R); //cin >> n >> L >> R; for(int i = 0; i < n; ++i) g[i+1].clear(); vector cc; for(int i = 0; i < n-1; ++i) { scanf("%d %d %d", &a, &b, &c); //cin >> a >> b >> c; g[a].push_back({b,c}); g[b].push_back({a,c}); cc.push_back(c); } sort(cc.begin(), cc.end()); cc.resize(unique(cc.begin(), cc.end()) - cc.begin()); // binary search int ans = -1; for(int s = 20; s >= 0; --s) { if (ans + (1 << s) >= cc.size()) continue; if (!can(cc[ans + (1 << s)])) ans += (1 << s); } if (ans+1 >= cc.size()) printf("-1\n"); //cout << "-1\n"; else printf("%d\n", cc[ans+1]); //cout << cc[ans+1] << "\n"; } return 0; }