动态电分治+二分
肯定要枚举所有点对，那么我们建出点分树降低树高，然后每个点存下点分树中所有子树到这个点的距离，然后二分+lower_bound就行了。
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5; namespace IO { const int Maxlen = N * 50; char buf[Maxlen], *C = buf; int Len; inline void read_in() { Len = fread(C, 1, Maxlen, stdin); buf[Len] = ' '; } inline void fread(int &x) { x = 0; int f = 1; while (*C < '0' || '9' < *C) { if(*C == '-') f = -1; ++C; } while ('0' <= *C && *C <= '9') x = (x << 1) + (x << 3) + *C - '0', ++C; x *= f; } inline void fread(long long &x) { x = 0; long long f = 1; while (*C < '0' || '9' < *C) { if(*C == '-') f = -1; ++C; } while ('0' <= *C && *C <= '9') x = (x << 1) + (x << 3) + *C - '0', ++C; x *= f; } inline void read(int &x) { x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0'; c = getchar(); } x *= f; } inline void read(long long &x) { x = 0; long long f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = (x << 1ll) + (x << 3ll) + c - '0'; c = getchar(); } x *= f; } } using namespace IO; int rd() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } struct edge { int nxt, to, w; } e[N << 1]; int n, q, cnt = 1, root, rt, tot, k; int head[N], size[N], f[N], Fa[N], dep[N], val[N << 1], vis[N], Log[N << 1], pos[N << 1], mn[N << 1][19], dis[N]; vector<int> ddis[N], DDis[N]; void link(int u, int v, int w) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].to = v; e[cnt].w = w; } void getroot(int u, int last, int S) { f[u] = 0; size[u] =1 ; for(int i = head[u]; i; i = e[i].nxt) if(!vis[e[i].to] && e[i].to != last) { getroot(e[i].to, u, S); size[u] += size[e[i].to]; f[u] = max(f[u], size[e[i].to]); } f[u] = max(f[u], S - size[u]); if(f[u] < f[root]) root = u; } int getsize(int u, int last) { int ret = 1; for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last && !vis[e[i].to]) ret += getsize(e[i].to, u); return ret; } void divide(int u) { vis[u] = 1; for(int i = head[u]; i; i = e[i].nxt) if(!vis[e[i].to]) { root = 0; getroot(e[i].to, u, getsize(e[i].to, u)); Fa[root] = u; divide(root); } } void dfs(int u, int last) { mn[pos[u] = ++tot][0] = dis[u]; for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last) { dis[e[i].to] = dis[u] + e[i].w; dep[e[i].to] = dep[u] + 1; dfs(e[i].to, u); mn[++tot][0] = dis[u]; } } int Dis(int u, int v) { int ret = dis[u] + dis[v]; if(pos[u] < pos[v]) swap(u, v); int x = Log[pos[u] - pos[v] + 1]; return ret - 2 * min(mn[pos[v]][x], mn[pos[u] - (1 << x) + 1][x]); } int ask(vector<int> &t, int x) { return upper_bound(t.begin(), t.end(), x) - t.begin(); } int check(int u, int x) { int ret = 0; for(int i = u; i; i = Fa[i]) { int d = ask(ddis[i], x - Dis(u, i)); ret += d; if(ret > 2 * n) return ret; } for(int i = Fa[u]; i; i = Fa[i]) if(Dis(u, i) <= x) ++ret; for(int i = u; Fa[i]; i = Fa[i]) { int d = ask(DDis[i], x - Dis(u, Fa[i])); ret -= d; } return ret; } int query(int u, int k) { int l = 0, r = 1e9 + 5, ret = 0; while(r - l > 1) { int mid = (l + r) >> 1; int tmp = check(u, mid); if(check(u, mid) >= k) r = ret = mid; else l = mid; } return ret; } int main() { char opt[2]; scanf("%s", opt); read(n); read(k); for(int i = 1; i < n; ++i) { int u, v, w; read(u); read(v); read(w); link(u, v, w); link(v, u, w); } dfs(1, 0); for(int i = 2; i <= tot; ++i) Log[i] = Log[i >> 1] + 1; for(int j = 1; j <= 18; ++j) for(int i = 1; i + (1 << j) - 1 <= tot; ++i) mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]); f[0] = 1e9; getroot(1, 0, getsize(1, 0)); rt = root; divide(root); for(int i = 1; i <= n; ++i) { for(int j = Fa[i]; j; j = Fa[j]) ddis[j].push_back(Dis(i, j)); for(int j = i; Fa[j]; j = Fa[j]) DDis[j].push_back(Dis(i, Fa[j])); } for(int i = 1; i <= n; ++i) { sort(ddis[i].begin(), ddis[i].end()); sort(DDis[i].begin(), DDis[i].end()); } for(int i = 1; i <= n; ++i) printf("%d ", query(i, k)); return 0; }