考虑点分树。
求出每个重心所管辖的范围内的每个点到它的距离，建成点分树。
查询时二分答案，然后问题就转化为求到x的距离<=d的点的个数。
在点分树上暴力往上跑就行了，注意去重。
时间复杂度：O(nlog3n)
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<vector> 6 #include<map> 7 using namespace std; 8 inline char nc(){ 9 static char buf[100000],*p1=buf,*p2=buf; 10 if(p1==p2){ 11 p2=(p1=buf)+fread(buf,1,100000,stdin); 12 if(p1==p2)return EOF; 13 } 14 return *p1++; 15 } 16 inline void Read(int& x){ 17 char c=nc(); 18 for(;c<'0'||c>'9';c=nc()); 19 for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc()); 20 } 21 int Len; 22 char S[30]; 23 inline void Print(int x){ 24 if(x==0)putchar(48); 25 for(Len=0;x;x/=10)S[++Len]=x%10; 26 for(;Len;)putchar(S[Len--]+48);putchar(' '); 27 } 28 #define N 100010 29 vector<int>g[N],g1[N],g2[N]; 30 map<int,int>Dist[N]; 31 struct Edge{ 32 int t,nx,w; 33 }e[N<<1]; 34 int Num,i,j,k,n,m,x,y,h[N],f[N],Top[N],Son[N],s[N],d[N],D[N],Sum,F[N],p[N],Rt,z,l; 35 bool b[N]; 36 inline int _Max(int x,int y){return x<y?y:x;} 37 inline void Add(int x,int y,int z){ 38 e[++Num].t=y;e[Num].w=z;e[Num].nx=h[x];h[x]=Num; 39 } 40 inline void Dfs1(int x,int F){ 41 f[x]=F;d[x]=d[F]+1;s[x]=1; 42 for(int i=h[x];i;i=e[i].nx) 43 if(e[i].t!=F){ 44 D[e[i].t]=D[x]+e[i].w; 45 Dfs1(e[i].t,x); 46 s[x]+=s[e[i].t]; 47 if(s[e[i].t]>s[Son[x]])Son[x]=e[i].t; 48 } 49 } 50 inline void Dfs2(int x,int tp){ 51 Top[x]=tp; 52 if(Son[x])Dfs2(Son[x],tp); 53 for(int i=h[x];i;i=e[i].nx) 54 if(e[i].t!=f[x]&&e[i].t!=Son[x])Dfs2(e[i].t,e[i].t); 55 } 56 inline void Get_root(int x,int Fa){ 57 F[x]=0;s[x]=1; 58 for(int i=h[x];i;i=e[i].nx) 59 if(e[i].t!=Fa&&!b[e[i].t]){ 60 Get_root(e[i].t,x); 61 s[x]+=s[e[i].t]; 62 F[x]=_Max(F[x],s[e[i].t]); 63 } 64 F[x]=_Max(F[x],Sum-s[x]); 65 if(F[x]<F[Rt])Rt=x; 66 } 67 inline void Dfs3(int l,int x,int F,int y){ 68 for(int i=h[x];i;i=e[i].nx) 69 if(!b[e[i].t]&&e[i].t!=F)Dfs3(l,e[i].t,x,y+e[i].w); 70 } 71 inline int Lca(int x,int y){ 72 while(Top[x]!=Top[y]) 73 if(d[Top[x]]>d[Top[y]])x=f[Top[x]];else y=f[Top[y]]; 74 return d[x]<d[y]?x:y; 75 } 76 inline int Get_dist(int x,int y){ 77 int L=Lca(x,y); 78 return D[x]+D[y]-(D[L]<<1); 79 } 80 inline void Solve(int x){ 81 b[x]=1;Dfs3(x,x,0,0); 82 for(int i=h[x];i;i=e[i].nx) 83 if(!b[e[i].t]){ 84 Sum=s[x];F[Rt=0]=Sum;Get_root(e[i].t,0); 85 p[Rt]=x;Solve(Rt); 86 } 87 } 88 inline int Find1(int x,int y){ 89 int l=0,r=g1[x].size()-1,Mid; 90 while(l<=r){ 91 Mid=l+r>>1; 92 if(g1[x][Mid]>y)r=Mid-1;else l=Mid+1; 93 } 94 return r+1; 95 } 96 inline int Find2(int x,int y){ 97 int l=0,r=g2[x].size()-1,Mid; 98 while(l<=r){ 99 Mid=l+r>>1; 100 if(g2[x][Mid]>y)r=Mid-1;else l=Mid+1; 101 } 102 return r+1; 103 } 104 inline int Calc(int x,int y){ 105 int Ans=0,X=x,l=x; 106 for(;x;x=p[x]){ 107 Ans+=Find1(x,y-Dist[X][x]); 108 if(x!=X)Ans-=Find2(l,y-Dist[X][x]); 109 l=x; 110 } 111 return Ans; 112 } 113 inline int Work(int x){ 114 int l=0,r=n*10000,Mid,Ans; 115 while(l<=r){ 116 Mid=l+r>>1; 117 if(Calc(x,Mid)-1<k)l=Mid+1;else Ans=Mid,r=Mid-1; 118 } 119 return Ans; 120 } 121 int main() 122 { 123 Read(n);Read(k); 124 for(i=1;i<n;i++)Read(x),Read(y),Read(z),Add(x,y,z),Add(y,x,z); 125 Dfs1(1,0);Dfs2(1,1); 126 Sum=n;F[Rt=0]=Sum;Get_root(1,0);Solve(Rt); 127 for(i=1;i<=n;i++) 128 for(j=p[i];j;j=p[j]) 129 Dist[i][j]=Get_dist(i,j); 130 for(i=1;i<=n;i++) 131 for(j=l=i;j;j=p[j]){ 132 g1[j].push_back(Dist[i][j]); 133 if(j!=i)g2[l].push_back(Dist[i][j]); 134 l=j; 135 } 136 for(i=1;i<=n;i++)sort(g1[i].begin(),g1[i].end()),sort(g2[i].begin(),g2[i].end()); 137 for(i=1;i<=n;i++)Print(Work(i)); 138 return 0; 139 }