Submission #67554591

---

Source Code Expand

#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops,inline")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll tmp=1;
    for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
    return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

const int N=2e5+5;
const int K=25;
const int C=1e9;

typedef array<int,4> arr;


vector<int> ed[N];
pii dist[N][K][2];


void solve()
{
    int n,k;
    cin>>n>>k;
    rep1(i,n)
    {
        ed[i].clear();
    }
    rep1(i,n-1)
    {
        int u,v;
        cin>>u>>v;
        ed[u].pb(v);
        ed[v].pb(u);
    }

    priority_queue<arr,vector<arr>,greater<arr> > pq;
    rep1(i,n) rep(j,k) rep(t,2) dist[i][j][t]={C,-1};
    dist[1][0][0].F=0;
    pq.push({0,1,0,0});
    auto upd=[&](int x,int r,pii val)
    {
        rep(i,2)
        {
            if(val.F<dist[x][r][i].F)
            {
                swap(val,dist[x][r][i]);
                pq.push({dist[x][r][i].F,x,r,i});
            }
            if(dist[x][r][i].S==val.S) break;
        }
    };
    while(!pq.empty())
    {
        auto [d,x,r,p]=pq.top();pq.pop();

        if(dist[x][r][p].F<d) continue;
        int s=dist[x][r][p].S;

        for(int v:ed[x])
        {
            if(r!=0&&v==s) continue;
            int to=(r+1)%k;
            upd(v,to,pii(d+1,x));
        }
    }
    for(int i=2;i<=n;i++)
    {
        if(dist[i][0][0].F>=C) cout<<"-1";
        else cout<<dist[i][0][0].F/k;
        cout<<" \n"[i==n];
    }
}

signed main()
{
    MottoHayaku

    int t;
    cin>>t;
    //t=1;
    while(t--)
    {
        solve();
    }
}

Submission Info

Judge Result