BZOJ2051 : A Problem For Fun

时间:2021-06-10 19:09:52

树的点分治,将点分治的过程记录下来,每一个分治结构按到分治中心的距离维护所有点。

对于一个点二分答案,然后在$O(\log n)$个分治结构中二分查找,时间复杂度$O(n\log^3n)$。

#include<cstdio>
#include<algorithm>
const int N=50010,M=1000010;
int n,m,i,x,y,z,g[N],nxt[N<<1],v[N<<1],w[N<<1],ok[N<<1],ed=1;
int son[N],f[N],size,now,cnt;
int G[N],NXT[M],V[2][M],W[M],ED,rl[N],rr[N],el[M],er[M],q[M<<1],tot;
inline void add(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],ok[ed]=1,g[x]=ed;}
inline void ADD(int x,int y,int z,int w){V[0][++ED]=y;V[1][ED]=z;W[ED]=w;NXT[ED]=G[x];G[x]=ED;}
void findroot(int x,int pre){
son[x]=1;f[x]=0;
for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre){
findroot(v[i],x);
son[x]+=son[v[i]];
if(son[v[i]]>f[x])f[x]=son[v[i]];
}
if(size-son[x]>f[x])f[x]=size-son[x];
if(f[x]<f[now])now=x;
}
void dfs(int x,int pre,int dis){
q[++tot]=dis;
for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre)dfs(v[i],x,dis+w[i]);
}
void dfs2(int x,int pre,int dis){
ADD(x,now,cnt,dis);
q[++tot]=dis;
for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre)dfs2(v[i],x,dis+w[i]);
}
void solve(int x){
int i;
q[rl[x]=++tot]=0;
for(i=g[x];i;i=nxt[i])if(ok[i])dfs(v[i],x,w[i]);
std::sort(q+rl[x],q+tot+1);
rr[x]=tot;
for(i=g[x];i;i=nxt[i])if(ok[i]){
el[++cnt]=tot+1;
dfs2(v[i],x,w[i]);
std::sort(q+el[cnt],q+tot+1);
er[cnt]=tot;
}
for(i=g[x];i;i=nxt[i])if(ok[i])ok[i^1]=0,f[0]=size=son[v[i]],findroot(v[i],now=0),solve(now);
}
inline int ask(int L,int r,int x){
int l=L,t=l-1,mid;
while(l<=r)if(q[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;
return t-L+1;
}
inline int query(int x,int k){
int t=ask(rl[x],rr[x],k)-1;
for(int i=G[x];i;i=NXT[i])t+=ask(rl[V[0][i]],rr[V[0][i]],k-W[i])-ask(el[V[1][i]],er[V[1][i]],k-W[i]);
return t;
}
inline int getans(int x){
int l=1,r=10000*(n-1),mid;
while(l<r)if(query(x,mid=(l+r)>>1)<m)l=mid+1;else r=mid;
return l;
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
f[0]=size=n;findroot(1,now=0);solve(now);
for(i=1;i<=n;i++)printf("%d\n",getans(i));
return 0;
}