传送门

思路：要求找一个最小Gg值，当 K = 1 时，我们知道这个点一定在直径上面，要使 Gg 最小，则该点到直径的两个端点距离的最大值最小。

DFS求直径：随意找一个点为起点，距离这个点最远的点就是直径的一个端点S，然后在以S为起点DFS，距离S距离最远的点就是直径的另一个端点E。

我们要记录一个结点的dp值  dp [ i ] 表示以 i 为根结点的子树上的所有结点距离 father[ i ] 的最大值。
以树的中心为起点，我们利用优先队列进行 K 次出队列的操作，最后队列顶端的 dp 值就是答案，如果不存在答案即为0。

代码：

///#include<bits/stdc++.h>
///#include<unordered_maps>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>

#define MT(a, b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai = acos(-1.0);
const double E = 2.718281828459;
const int mod = 20190414;
const ll INF = 0x3f3f3f3f3f3f;

int t, n, k;

struct node {
    int e;
    ll c;
    int p;

    bool friend operator<(node a, node b) {
        return a.c < b.c;
    }
} load[200005];

int head[100005], sign;

void add_edge(int s, int e, ll c) {
    load[++sign] = node{e, c, head[s]};
    head[s] = sign;
}

ll maxn;
int des, start;
int father[100005];
ll dis[100005];

void dfs(int s, int pre) {
    if (dis[s] > maxn) {
        des = s;
        maxn = dis[s];
    }
    for (int i = head[s], e; ~i; i = load[i].p) {
        e = load[i].e;
        if (e ^ pre) {
            father[e] = s;
            dis[e] = dis[s] + load[i].c;
            dfs(e, s);
        }
    }
}

int get_point() {
    /// start 起点  des 终点
    maxn = 0;
    father[1] = -1;
    start = 1;
    dis[1] = 0;
    dfs(1, -1);

    start = des;
    maxn = 0;
    father[start] = -1;
    dis[start] = 0;
    dfs(start, -1);

    ll minn = INF;
    int point, x = des;
    while (x != -1) {
        maxn = max(dis[x], dis[des] - dis[x]);
        if (maxn < minn) {
            minn = maxn;
            point = x;
        }
        x = father[x];
    }
    return point;
}

ll max_dis[100005];
bool vis[100005];


ll dfs_len(int s, int pre) {
    //max_dis[s] = 0;
    ll ans = 0;
    for (int i = head[s], e; ~i; i = load[i].p) {
        e = load[i].e;
        if (e ^ pre) {
            ll temp = dfs_len(e, s) + load[i].c;
            ans = max(ans, temp);
            max_dis[e] = temp;
        }
    }
    return ans;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        int s, e;
        ll c;
        scanf("%d %d", &n, &k);
        sign = 0;
        for (int i = 1; i <= n; i++) {
            vis[i] = 0;
            head[i] = -1;
        }
        for (int i = 1; i < n; i++) {
            scanf("%d %d %lld", &s, &e, &c);
            add_edge(s, e, c);
            add_edge(e, s, c);
        }
        int point = get_point();
        dfs_len(point, -1);
        priority_queue<node> q;
        q.push(node{point, max_dis[point], 0});
        vis[point] = 1;
        for (int i = 1; i <= k; i++) {
            node w = q.top();
            q.pop();
            for (int j = head[w.e]; ~j; j = load[j].p) {
                e = load[j].e;
                if (!vis[e]) {
                    q.push(node{e, max_dis[e], 0});
                    vis[e] = 1;
                }
            }
        }
        if (q.empty()) {
            printf("0\n");
        } else {
            printf("%lld\n", q.top().c);
        }
    }
}