树
这题一复制题面就卡住是什么鬼。
N点带边权树，求每个点到其他点距离第k小的值。
Sol
考虑动态点分，每个点开两个vector，v1存点分治时它到所有子节点的距离和，v2存它的点分树上父亲到他的所有子节点的距离和。
假设一个点x,他的父亲fx
那么与x距离不超过k的点就是它v1[x]中<=k的数的数量，减去v2[x]中<=k-dis(x,fx)的，加上v1[fx]中<=k-dis(x,fx)的.....
这里减去时因为那些点既在x处被算到了，又在fx处被算到了。
可能有疑问，那f[fx]处被算到的呢？
考虑x处减完后,此时答案为只在x处能被算到的点。因为f[fx]处算到那么fx处也会被算到（fx与x在f[fx]的同一棵子树内）
那么就好了。
那么这题，二分答案然后pd<=mid的数的数量即可。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<vector> 8 #define maxn 50005 9 #define inf 1e9 10 using namespace std; 11 int n,K,head[maxn],tot,sz[maxn],f[maxn]; 12 int deep[maxn],rt,siz,vis[maxn],par[maxn],st[maxn*2][22],sc; 13 int len[maxn],Sum,fi[maxn],L[maxn*2]; 14 vector<int>G[maxn],g[maxn]; 15 struct node{ 16 int v,nex,w; 17 }e[maxn*2]; 18 void add(int t1,int t2,int t3){ 19 e[++tot].v=t2;e[tot].w=t3;e[tot].nex=head[t1];head[t1]=tot; 20 } 21 void DFS(int k,int fa){ 22 fi[k]=++sc;st[sc][0]=len[k]; 23 deep[k]=deep[fa]+1; 24 for(int i=head[k];i;i=e[i].nex){ 25 if(e[i].v==fa)continue; 26 len[e[i].v]=len[k]+e[i].w; 27 DFS(e[i].v,k); 28 st[++sc][0]=len[k]; 29 } 30 } 31 void init(){ 32 DFS(1,0); 33 34 for(int j=1;j<=20;j++) 35 for(int i=1;i+(1<<j)<=sc;i++)st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]); 36 for(int i=2;i<=sc;i++)L[i]=L[i/2]+1; 37 } 38 void findr(int k,int fa){ 39 40 sz[k]=1; 41 f[k]=0; 42 for(int i=head[k];i;i=e[i].nex){ 43 if(vis[e[i].v]||e[i].v==fa)continue; 44 findr(e[i].v,k); 45 sz[k]+=sz[e[i].v]; 46 f[k]=max(f[k],sz[e[i].v]); 47 } 48 f[k]=max(f[k],siz-sz[k]); 49 if(f[k]<f[rt])rt=k; 50 } 51 int lca(int a,int b){ 52 int t1=fi[a],t2=fi[b]; 53 if(t1>t2)swap(t1,t2); 54 int t=L[t2-t1+1]; 55 return min(st[t1][t],st[t2-(1<<t)+1][t]); 56 } 57 int dis(int x,int y){ 58 int l=lca(x,y); 59 return len[x]+len[y]-2*l; 60 } 61 void dfs(int k,int fa,int sk,int sf){ 62 G[sk].push_back(dis(k,sk)); 63 if(sf){ 64 g[sk].push_back(dis(k,sf)); 65 } 66 sz[k]=1; 67 for(int i=head[k];i;i=e[i].nex){ 68 if(vis[e[i].v]||e[i].v==fa)continue; 69 sz[k]+=sz[e[i].v]; 70 dfs(e[i].v,k,sk,sf); 71 } 72 } 73 void work(int k,int fa){ 74 vis[k]=1; 75 dfs(k,0,k,fa); 76 for(int i=head[k];i;i=e[i].nex){ 77 if(vis[e[i].v])continue; 78 rt=0;siz=sz[k];findr(e[i].v,k); 79 par[rt]=k;work(rt,k); 80 } 81 82 } 83 int askG(int k,int v){ 84 int l=0,r=G[k].size()-1; 85 while(l<r){ 86 int mid=l+r+1>>1; 87 if(G[k][mid]<=v)l=mid; 88 else r=mid-1; 89 } 90 return G[k][l]<=v?l+1:l; 91 } 92 int askg(int k,int v){ 93 int l=0,r=g[k].size()-1; 94 while(l<r){ 95 int mid=l+r+1>>1; 96 if(g[k][mid]<=v)l=mid; 97 else r=mid-1; 98 } 99 return g[k][l]<=v?l+1:l; 100 } 101 int calc(int k,int v){ 102 int fi=k,ans=0; 103 while(k){ 104 ans=ans+askG(k,v-dis(k,fi)); 105 if(par[k])ans-=askg(k,v-dis(par[k],fi)); 106 k=par[k]; 107 } 108 return ans; 109 } 110 int main(){ 111 cin>>n>>K;K++; 112 113 for(int i=1,t1,t2,t3;i<n;i++){ 114 scanf("%d%d%d",&t1,&t2,&t3); 115 add(t1,t2,t3);add(t2,t1,t3);Sum+=t3; 116 } 117 init(); 118 f[0]=inf;rt=0;siz=n;findr(1,0); 119 work(rt,0); 120 for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end()),sort(g[i].begin(),g[i].end()); 121 for(int i=1;i<=n;i++){ 122 int l=0,r=Sum; 123 while(l<r){ 124 int mid=l+r>>1; 125 if(calc(i,mid)>=K)r=mid; 126 else l=mid+1; 127 } 128 printf("%d ",l); 129 } 130 return 0; 131 }