题目
多次询问距离一个点的第 (k) 小距离。
分析
点分树+二分+线段树
首先，我们要明确的是，求第 (k) 小，是可以二分答案然后直接遍历判断个数的。
于是这就启示我们直接二分答案，那么这道题目就变成模板了，也就是求距离 (x) 小于等于 (mid) 的点的个数。
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;bool f=false;char ch=getchar();
while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
#define ll long long
const int N=5e5+5,INF=1e9+7;
int n,k,m,val[N],Ans;
int head[N],to[N<<1],nex[N<<1],idx;
int st[N][21],pos[N],Euler,fa[N],lg[N],dis[N],dep[N];
bool vis[N];
vector<int> c[2][N];
inline void add(int u,int v,int w){
nex[++idx]=head[u];
to[idx]=v;
val[idx]=w;
head[u]=idx;
return ;
}
void EulerDfs(int x,int f){
fa[x]=f,dep[x]=dep[f]+1,st[++Euler][0]=x;pos[x]=Euler;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==f) continue;
dis[y]=dis[x]+val[i],EulerDfs(y,x);
st[++Euler][0]=x;
}
return ;
}
inline int GetMin(int x,int y){return dep[x]<dep[y]?x:y;}
void GetST(){
for(int i = 1; i <= Euler; ++i) lg[i] = 31 - __builtin_clz(i);
for(int j=1;(1<<j)<=Euler;j++) for(int i=1;i+(1<<j)<=Euler;i++) st[i][j]=GetMin(st[i][j-1],st[i+(1<<(j-1))][j-1]);
return ;
}
inline int QueryDis(int x,int y){
if(pos[x]>pos[y]) swap(x,y);
const int ql=pos[x],qr=pos[y],tmp=lg[qr-ql+1];
const int lca=GetMin(st[ql][tmp],st[qr-(1<<tmp)+1][tmp]);
return dis[x]+dis[y]-dis[lca]-dis[lca];
}
int FMax,Max,Root,Size,siz[N];
void GetRoot(int x,int f){
int Max=0;siz[x]=1;
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(y==f||vis[y]) continue;
GetRoot(y,x);siz[x]+=siz[y];
Max=max(Max,siz[y]);
}
Max=max(Max,Size-siz[x]);
if(Max<=FMax) FMax=Max,Root=x;
return ;
}
void Divide(int x){
vis[x]=true;siz[x]=(Size+1)*10;
c[0][x].resize(siz[x]+1);
c[1][x].resize(siz[x]+1);
for(int i=head[x];i;i=nex[i]){
int y=to[i];
if(vis[y]) continue;
Size=siz[y],Root=y,FMax=INF,GetRoot(y,0),fa[Root]=x,Divide(Root);
}
return ;
}
inline void Add(int typ,int u,int x,int v){x++;for(;x<=siz[u];x+=(x&(-x))) c[typ][u][x]+=v;return ;}
inline int Ask(int typ,int u,int x){x++;int res=0;x=min(x,siz[u]);for(;x;x-=(x&(-x))) res+=c[typ][u][x];return res;}
inline void Modify(int x,int v){
for(int u=x;u;u=fa[u]) Add(0,u,QueryDis(x,u),v);
for(int u=x;fa[u];u=fa[u]){
Add(1,u,QueryDis(x,fa[u]),v);
}
return ;
}
inline bool Query(int x,int y){
Ans=Ask(0,x,y)-1;
for(int u=x;fa[u];u=fa[u]){
const int Dis=QueryDis(x,fa[u]);
if(y>=Dis) Ans+=Ask(0,fa[u],y-Dis)-Ask(1,u,y-Dis);
}
return Ans>=k;
}
signed main(){
read(n),read(k);
for(int i=1;i<n;i++){
int u,v,w;
read(u),read(v),read(w);
add(u,v,w),add(v,u,w);
}
EulerDfs(1,0);
GetST();
Size=n,Root=1,FMax=INF;
GetRoot(1,0);fa[Root]=0;Divide(Root);
for(int i=1;i<=n;i++) Modify(i,1);
for(int i=1;i<=n;i++){
int l=0,r=n*10+1,res=0;
while(l<r){
int mid=(l+r)>>1;
int tmp=Query(i,mid);
if(tmp) r=mid;
else l=mid+1;
}
write(r),putchar('
');
}
return 0;
}