BZOJ4317: Atm的树+2051+2117

BZOJ4317: Atm的树+2051+2117

https://lydsy.com/JudgeOnline/problem.php?id=4317

分析:

• 二分答案之后就变成震波那道题了。
• 冷静一下可以发现，这题没有修改，直接维护一个有序表每次二分就完事了。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 15050
int head[N],to[N<<1],nxt[N<<1],val[N<<1],cnt,n,K;
int siz[N],fk[N],root;
int fa[N][15],dep[N],dis[N][15],used[N],tot;
int bg[N][2],ed[N][2],pp;
int a[N*30];
inline void add(int u,int v,int w) {
    to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
void gr(int x,int y) {
    int i;
    siz[x]=1; fk[x]=0;
    for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]) {
        gr(to[i],x); siz[x]+=siz[to[i]];
        fk[x]=max(fk[x],siz[to[i]]);
    }
    fk[x]=max(fk[x],tot-siz[x]);
    if(fk[x]<fk[root]) root=x;
}
void gd(int x,int y,int rt,int d) {
    int i;
    a[++pp]=d; a[pp+tot]=dis[x][dep[x]];
    fa[x][++dep[x]]=rt; dis[x][dep[x]]=d;
    for(i=head[x];i;i=nxt[i]) if(to[i]!=y&&!used[to[i]]) {
        gd(to[i],x,rt,d+val[i]);
    }
}
void solve(int x) {
    used[x]=1;
    int i,all=tot;
    bg[x][0]=pp+1, bg[x][1]=pp+tot+1, ed[x][0]=pp+tot, ed[x][1]=pp+tot+tot;
    gd(x,0,x,0);
    sort(a+bg[x][0],a+ed[x][0]+1);
    sort(a+bg[x][1],a+ed[x][1]+1);
    pp+=tot;
    for(i=head[x];i;i=nxt[i]) if(!used[to[i]]) {
        root=0;
        tot=siz[to[i]]; if(tot>siz[x]) tot=all-siz[x];
        gr(to[i],x); solve(root);
    }
}
int find(int x,int o,int k) {
    if(!x) return 0;
    int l=bg[x][o],r=ed[x][o]+1;
    while(l<r) {
        int mid=(l+r)>>1;
        if(a[mid]>k) r=mid;
        else l=mid+1;
    }
    return l-bg[x][o];
}
int query(int x,int k) {
    int i,re=0;
    for(i=dep[x];i;i--) {
        if(k>=dis[x][i]) {
            re+=find(fa[x][i],0,k-dis[x][i]);
            re-=find(fa[x][i+1],1,k-dis[x][i]);
        }
    }
    return re;
}
int main() {
    scanf("%d%d",&n,&K); K++;
    int i,x,y,z;
    for(i=1;i<n;i++) {
        scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);
    }
    fk[0]=1<<30; tot=n; gr(1,0); solve(root);
    for(i=1;i<=n;i++) {
        int l=0,r=n*10+1;
        while(l<r) {
            int mid=(l+r)>>1;
            int tmp=query(i,mid);
            if(tmp>=K) r=mid;
            else l=mid+1;
        }
        printf("%d\n",l);
    }
}

BZOJ4317: Atm的树+2051+2117

原文：https://www.cnblogs.com/suika/p/10164396.html