题目大意：给你一棵$n$个点的带权树和正整数$K$，求每个点到其它所有点距离中第$K$大的数值。
其中，边权$≤10000$，$n≤50000$。
我们通过原树构建一棵点分治树，令$fa[u]$为$u$在点分树上的$father$。
对于每个点$u$，我们维护两个有序数组$f$和$g$。
其中$f[i]$表示以$u$为根的点分树中，距离$u$第$i$近的距离。（显然里面有$siz[u]$个数值）
$g[i]$表示以$u$为根的点分树中，距离$fa[u]$第i近的距离。
我们二分答案，设当前二分到的值为$p$，我们要求所有与$u$距离$≤p$的数量。
然后答案显然为$\sum_{v∈ancestor[u]} (\sum_{f[v][i]≤p-dis(v,u)}1-\sum_{g[v][i]≤p-dis(fa[v],u)}1)$
这样单次询问的时间复杂度显然是$O(log^3n)$的。
然后时间复杂度就是$O(n\ log^3\ n)$。
完结撒花
#include<bits/stdc++.h>
#define M 50005
#define INF 19890604
using namespace std; struct edge{int u,v,next;}e[M*]={}; int head[M]={},use=;
void add(int x,int y,int z){use++;e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use;}
int n,k;
int f[M][]={},d[M]={},dep[M]={}; void dfs(int x,int fa){
f[x][]=fa; dep[x]=dep[fa]+;
for(int i=;i<;i++) f[x][i]=f[f[x][i-]][i-];
for(int i=head[x];i;i=e[i].next) if(e[i].u!=fa){
d[e[i].u]=d[x]+e[i].v;
dfs(e[i].u,x);
}
}
int getlca(int x,int y){
if(dep[x]<dep[y]) swap(x,y); int cha=dep[x]-dep[y];
for(int i=;~i;i--) if((<<i)&cha) x=f[x][i];
for(int i=;~i;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
if(x==y) return x; return f[x][];
}
int getdis(int x,int y){
int lca=getlca(x,y);
return d[x]+d[y]-*d[lca];
} int vis[M]={},siz[M]={},minn=INF,minid=;
void dfssiz(int x,int fa){
siz[x]=;
for(int i=head[x];i;i=e[i].next)
if(e[i].u!=fa&&vis[e[i].u]==){
dfssiz(e[i].u,x);
siz[x]+=siz[e[i].u];
}
}
void dfsmin(int x,int fa,int fsiz){
int maxn=fsiz-siz[x];
for(int i=head[x];i;i=e[i].next)
if(e[i].u!=fa&&vis[e[i].u]==){
dfsmin(e[i].u,x,fsiz);
maxn=max(maxn,siz[e[i].u]);
}
if(maxn<minn) minn=maxn,minid=x;
}
int makeroot(int x){
dfssiz(x,);
minn=INF; minid=;
dfsmin(x,,siz[x]);
return minid;
}
vector<int> F[M],G[M]; void addvec(int x,int fa,int X,int FA,int nowdis){
F[X].push_back(getdis(x,X));
G[X].push_back(getdis(x,FA));
for(int i=head[x];i;i=e[i].next)
if(e[i].u!=fa&&vis[e[i].u]==)
addvec(e[i].u,x,X,FA,nowdis+e[i].v);
}
int fa[M]={};
void build(int x,int Fa){
x=makeroot(x); vis[x]=; fa[x]=Fa;
addvec(x,fa[x],x,fa[x],);
sort(F[x].begin(),F[x].end());
sort(G[x].begin(),G[x].end());
for(int i=head[x];i;i=e[i].next) if(vis[e[i].u]==){
build(e[i].u,x);
}
} bool check(int x,int mid){
int res=-,X=x;
for(;x;x=fa[x]){ res+=upper_bound(F[x].begin(),F[x].end(),mid-getdis(X,x))-F[x].begin();
if(fa[x]) res-=upper_bound(G[x].begin(),G[x].end(),mid-getdis(X,fa[x]))-G[x].begin();
}
return res>=k;
} int main(){
scanf("%d%d",&n,&k);
for(int i=;i<n;i++){
int x,y,z; scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
dfs(,);
build(,);
for(int i=;i<=n;i++){
int l=,r=*n;
while(l<r){
int mid=(l+r)>>;
if(check(i,mid)) r=mid;
else l=mid+;
}
printf("%d\n",l);
}
}