Submission #67544807

---

Source Code Expand

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define bi __int128_t
#define lb(x) ((x)&(-(x)))
#define gp(i,j) (((i)>>(j-1))&1)
#define ppc __builtin_popcount
using namespace std;
const int N=2e5+10,K=22,mod=998244353;
const ll inf=1e18+10;
void Add(int &a,int b){a+=b;if(a>=mod) a-=mod;}
void Sub(int &a,int b){a-=b;if(a<0) a+=mod;}
void Mul(int &a,int b){a=1ll*a*b%mod;}
int qp(int a,int b){
    int x=1;
    while(b){
        if(b&1) Mul(x,a);
        Mul(a,a);b>>=1;
    }return x;
}
int d[N],fa[N],dep[N],dfn[N],siz[N],dc=0;
vector<int> E[N];
set<pii> st[N];
int n,k;
int id(int u,int x){
    return (x-1)*n+u;
}
void dfs(int u,int pa){
    fa[u]=pa;dep[u]=dep[pa]+1;
    dfn[u]=++dc;siz[u]=1;
    for(auto v:E[u]){
        if(v==pa) continue;
        dfs(v,u);siz[u]+=siz[v];
    }
}
queue<int> q;
void upd(int l,int r,int D,int p){
    if(D>n) return ;
    //cout<<l<<' '<<r<<' '<<D<<' '<<p<<endl;
    auto it=st[D].lower_bound(mk(l,0));
    while((*it).fi<=r){
        int id=(*it).se;
        d[id]=d[p]+1;q.push(id);
        st[D].erase(it);
        it=st[D].lower_bound(mk(l,0));
        //cout<<(*it).fi<<endl;
    }//cout<<endl;
}
void slv(){
    cin>>n>>k;
    dc=0;
    for(int i=1;i<=n;i++)
        E[i].clear(),st[i].clear(),d[i]=1e9;
    for(int i=1;i<=n;i++)
        st[i].insert(mk(n+1,0));
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        E[u].push_back(v);
        E[v].push_back(u);
    }dfs(1,0);
    for(int i=1;i<=n;i++){
        //cout<<i<<' '<<dep[i]<<endl;
        st[dep[i]].insert(mk(dfn[i],i));
    }
    while(!q.empty()) q.pop();
    d[1]=0;q.push(1);
    while(!q.empty()){
        int p=q.front();q.pop();
        int now=p,la=0;
        for(int i=0;i<=k;i++){
            if(!now) break;
            if(!la)
                upd(dfn[now],dfn[now]+siz[now]-1,dep[now]+(k-i),p);
            else
                upd(dfn[now],dfn[la]-1,dep[now]+(k-i),p),
                upd(dfn[la]+siz[la],dfn[now]+siz[now]-1,dep[now]+(k-i),p);
            la=now;now=fa[now];
        }
    }
    for(int i=2;i<=n;i++){
        if(d[i]>=1e9) d[i]=-1;
        cout<<d[i]<<' ';
    }cout<<endl;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;cin>>t;
    while(t--) slv();
    cout.flush();
    return 0;
}

Submission Info

Judge Result