题解：AT_abc414_f [ABC414F] Jump Traveling

· · 题解

提供一种和题解截然不同的思路，本写法的时间复杂度与 k 的值域无关，时间复杂度为 O(n\log n) 。

一种简单的暴力思路是直接将所有的距离为 k 的点对进行连边，然后直接在新建出来的图上跑一边 bfs 即可。但显然这样的做法会被一个菊花图卡掉。

那我们考虑如何优化这个过程。原图给出的是一棵树，我们不难想到一种处理树上路径问题的工具树分治，在树分治的过程中找到距离为 k 的点对是平凡的，我们考虑如何实现连边过程，这里笔者选择了边分治，实现起来比较简单。

具体来说，我们在找到当前的分治边后，对于划分成的两个连通块，我们称其分别为左块和右块，我们分别用对两个块深度为 i 的节点新开一个代表节点 Lid_i,Rid_i ，对于每一个新开的代表节点我们向它们所代表的真实节点连单向边，边权为 0 ，将左块深度为 i 的点向 Rid_{k-i} 连一条边权为 1 的有向边，这样能够实现我们的连边操作。由于我们这个过程是在边分治的过程中进行的，所以总体连的边数 n\log n 级别的，最后我们在新建出的图上跑 01bfs 即可。总的时间复杂度为 O(n \log n) ，空间复杂度也为 n\log n 。

代码感觉细节还是不少的。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+10;
struct Road{int nex,to,dis;};
struct Graph{
    Road x[N];int head[N],p=1;
    void clear(int n){for(int i=1;i<=n;i++)head[i]=0;p=1;}
    void add(int a,int b,int c){
        x[++p].nex=head[a];
        x[p].to=b;x[p].dis=c;
        head[a]=p;
    }
}S,T,G;
int n,k,I,cnt;
void rebuild(int a,int fa){
    int B=3,w=a,t=0;
    for(int q=S.head[a];q;q=S.x[q].nex){
        int to=S.x[q].to;
        if(to==fa)continue;
        if(t==B){++cnt;T.add(w,cnt,0),T.add(cnt,w,0);w=cnt,t=1;}
        T.add(w,to,1);T.add(to,w,1);t++;
        rebuild(to,a);
    }
}
int rt,MAX,siz[N];
bitset<N>vis;
void Get_rt(int a,int fa,int n){
    siz[a]=1;
    for(int q=T.head[a];q;q=T.x[q].nex){
        int o=T.x[q].to;
        if(o==fa||vis[q]||vis[q^1])continue;
        Get_rt(o,a,n);siz[a]+=siz[o];
        int k=max(siz[o],n-siz[o]);
        if(k<MAX)MAX=k,rt=q;
    }
}
int dep[N],id[N],Id[N];
void dfs(int a,int fa,int dis,int op){
    if(dis>k)return ;

    if(op==0){
        if(id[dis]==0)id[dis]=++cnt;
        G.add(id[dis],a,0);
    }
    if(op==2&&Id[k-dis])G.add(a,Id[k-dis],1);
    if(op==1){
        if(Id[dis]==0)Id[dis]=++cnt;
        G.add(Id[dis],a,0);
    }
    if(op==3&&id[k-dis])G.add(a,id[k-dis],1);
    if(op==-1)id[dis]=Id[dis]=0;

    for(int q=T.head[a];q;q=T.x[q].nex){
        int o=T.x[q].to;
        if(o==fa||vis[q]||vis[q^1])continue;
        dfs(o,a,dis+T.x[q].dis,op);
    }
}
void work(int ls,int rs,int D){
    dfs(ls,rs,D,0);dfs(rs,ls,0,1);
    dfs(ls,rs,D,2);dfs(rs,ls,0,3);
    dfs(ls,rs,D,-1);dfs(rs,ls,0,-1);
}
void solve(int a,int n){
    if(n==1)return ;
    MAX=1e9;Get_rt(a,0,n);
    int I=rt;vis[I]=vis[I^1]=1;
    int ls=T.x[I].to,rs=T.x[I^1].to,k=siz[ls];
    work(ls,rs,T.x[I].dis);
    solve(ls,k);solve(rs,n-k);
}
int f[N];
deque<int>z;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
int main(){
//  freopen("data.txt", "r", stdin);
//  freopen("test.txt", "w", stdout);
    int Time;Time=read();
    while(Time--){
        n=read(), k=read();
        for(int i=1;i<n;i++){
            int a,b;a=read();b=read();
            S.add(a,b,1);S.add(b,a,1);
        }
        cnt=n;rebuild(1,0);
        solve(1,cnt);
        for(int i=2;i<=cnt;i++)f[i]=-1;
        z.push_back(1);
        while(!z.empty()){
            int i=z.front();
            z.pop_front();
            for(int q=G.head[i];q;q=G.x[q].nex){
                int to=G.x[q].to,dis=G.x[q].dis;
                if(f[to]==-1){
                    f[to]=f[i]+dis;
                    if(dis==0)z.push_front(to);
                    else z.push_back(to);
                }
            }
        }
        for(int i=2;i<=n;i++)cout<<f[i]<<" ";cout<<"\n";
        for(int i=1;i<=T.p;i++)vis[i]=0;
        S.clear(n);T.clear(cnt);G.clear(cnt);
    }
    return 0;
}

笔者虽然没有见过相同思路的题目，但感觉这种在树分治过程中优化建图的方式还是可以有所扩展的，如果大家有见过相似题目的欢迎分享。