Submission #31416520

---

Source Code Expand

#include <atcoder/string>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)


void sort_tg_by(vector<vector<int>>& tg, vector<int>& by, int bound){
    int sz = 0;
    for(auto a : tg ) sz += a.size();
    vector<vector<pair<int,int>>> bucket(bound);
    rep(i,tg.size()) for(int v : tg[i]) bucket[by[v]].push_back(make_pair(i,v));
    for(auto& a : tg) a.clear();
    for(auto& b : bucket) for(auto [i,v] : b) tg[i].push_back(v);
}


vector<int> coord_compress_from_arr_by(vector<vector<int>>& tg, vector<int>& by, int bound){
    int n = tg.size();
    vector<int> sa_src;
    vector<int> sa_recover;
    rep(i,n){
        sa_recover.push_back(i);
        for(auto a : tg[i]){
            sa_src.push_back(by[a] + 1);
            sa_recover.push_back(-1);
        }
        sa_src.push_back(0);
    }
    auto sa = atcoder::suffix_array(sa_src, bound);

    vector<int> sorted_tg_idx;
    rep(i,sa.size()) if(sa_recover[sa[i]] != -1) sorted_tg_idx.push_back(sa_recover[sa[i]]);
    
    vector<int> res(n);
    for(int i=1; i<n; i++){
        res[sorted_tg_idx[i]] = res[sorted_tg_idx[i-1]];
        bool same = true;
        if(tg[sorted_tg_idx[i-1]].size() != tg[sorted_tg_idx[i]].size()){
            same = false;
        }
        else{
            rep(j,tg[sorted_tg_idx[i]].size()){
                if(by[tg[sorted_tg_idx[i-1]][j]] != by[tg[sorted_tg_idx[i]][j]]) same = false;
            }
        }
        if(!same) res[sorted_tg_idx[i]]++;
    }
    return res;
}


int main(){
    int N; cin >> N;
    vector<vector<int>> E(N);
    rep(i,N-1){
        int u,v; cin >> u >> v; u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    vector<int> parent(N, -1);
    vector<int> depth(N, -1);
    vector<int> bfs = {0};
    depth[0] = 0;
    rep(i,N){
        int p = bfs[i];
        for(int e : E[p]) if(depth[e] == -1){
            depth[e] = depth[p] + 1;
            parent[e] = p;
            bfs.push_back(e);
        }
    }

    int max_depth = *max_element(depth.begin(), depth.end());
    vector<vector<int>> from_depth(max_depth+2);
    rep(i,N) from_depth[depth[i]].push_back(i);

    vector<int> compressed(N, 0);
    vector<vector<int>> children_ordered(N);
    vector<vector<int>> Arr(N);

    rep(p,N) for(int c : E[p]) if(depth[p] < depth[c]) children_ordered[p].push_back(c);

    for(int d = max_depth; d >= 0; d--){
        auto& vtxs = from_depth[d];
        vector<vector<int>> children_ordered_part(vtxs.size());
        rep(i,vtxs.size()) children_ordered_part[i] = move(children_ordered[vtxs[i]]);
        sort_tg_by(children_ordered_part, compressed, from_depth[d+1].size());
        auto compressed_part = coord_compress_from_arr_by(children_ordered_part, compressed, from_depth[d+1].size());
        rep(i,vtxs.size()) children_ordered[vtxs[i]] = move(children_ordered_part[i]);
        rep(i,vtxs.size()) compressed[vtxs[i]] = compressed_part[i];
    }

    vector<int> ans;
    auto dfs = [&](auto self, int p) -> void {
        ans.push_back(depth[p]);
        for(int c : children_ordered[p]){
            self(self, c);
            ans.push_back(depth[p]);
        }
    };
    dfs(dfs, 0);

    rep(i,ans.size()){
        if(i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

Submission Info

Judge Result