二分答案后就转化为有多少个数到某点距离小于多少 这就是个裸的点分树啊 复杂度 O(nlog3n)
#include<cstdio> #include<cstdlib> #include<algorithm> #include<vector> using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=100005; struct edge{ int u,v,w,next; }G[N<<1]; int head[N],inum; inline void add(int u,int v,int w,int p){ G[p].u=u; G[p].v=v; G[p].w=w; G[p].next=head[u]; head[u]=p; } #define V G[p].v int fat[N][25],dis[N][25]; int del[N]; int size[N],sum,minv,rt; inline void Root(int u,int fa){ size[u]=1; int maxv=0; for (int p=head[u];p;p=G[p].next) if (V!=fa && !del[V]) Root(V,u),size[u]+=size[V],maxv=max(maxv,size[V]); maxv=max(maxv,sum-size[u]); if (maxv<minv) minv=maxv,rt=u; } int cur,cnt; inline void dfs(int u,int fa,int d){ fat[u][++*fat[u]]=cur; dis[u][++*dis[u]]=d; ++cnt; for (int p=head[u];p;p=G[p].next) if (V!=fa && !del[V]) dfs(V,u,d+G[p].w); } inline void Divide(int u){ del[u]=1; cur=u; fat[u][++*fat[u]]=u; dis[u][++*dis[u]]=0; for (int p=head[u];p;p=G[p].next) if (!del[V]){ cnt=0; dfs(V,u,G[p].w); size[V]=cnt; } for (int p=head[u];p;p=G[p].next) if (!del[V]){ sum=size[V],minv=1<<30,Root(V,0); Divide(rt); } } #define pb push_back vector<int> T[N],F[N]; inline int Bin(vector<int> &A,int B){ return upper_bound(A.begin(),A.end(),B)-A.begin(); } inline int count(int x,int d){ int ret=0; for (int j=1;j<=*fat[x];j++){ ret+=Bin(T[fat[x][j]],d-dis[x][j]); if (j!=1) ret-=Bin(F[fat[x][j-1]],d-dis[x][j]); } return ret; } int n,K; inline int Solve(int x){ int L=0,R=1<<30,MID; while (L+1<R) if (count(x,MID=(L+R)>>1)<K) L=MID; else R=MID; printf("%d\n",R); } int main(){ int iu,iv,iw; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(K); K++; for (int i=1;i<n;i++) read(iu),read(iv),read(iw),add(iu,iv,iw,++inum),add(iv,iu,iw,++inum); sum=n,minv=1<<30,Root(1,0); Divide(rt); for (int i=1;i<=n;i++){ reverse(fat[i]+1,fat[i]+*fat[i]+1),reverse(dis[i]+1,dis[i]+*dis[i]+1); for (int j=1;j<=*fat[i];j++){ T[fat[i][j]].pb(dis[i][j]); if (j!=1) F[fat[i][j-1]].pb(dis[i][j]); } } for (int i=1;i<=n;i++) sort(T[i].begin(),T[i].end()),sort(F[i].begin(),F[i].end()); // printf("%d\n",T[1].size()); for (int i=1;i<=n;i++) Solve(i); return 0; }