HLD code

hld.cc

#define DEBUG
#define LARGEINT

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <fmt/core.h>

using namespace __gnu_pbds;
using namespace std;

#ifdef LARGEINT
    #define int ll
#endif

typedef long long ll;

namespace basics {
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef pair<ld, ld> point;

    const long long mod = 1e9 + 7;
    // To remove randomization use 0 below:
    /* mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); */
    mt19937 rng(5);

    inline int ri(int x) { // from [0, n-1]
        return uniform_int_distribution<int>(0, x - 1)(rng);
    }

    inline ld rf() { // from [0, 1]
        return uniform_real_distribution<ld>(0, 1)(rng);
    }

    ll gcd(ll x, ll y) {
        if (x < y) return gcd(y, x);
        if (y == 0) return x;
        return gcd(y, x % y);
    }

    ll modexp(ll x, ll ex) {
        ll ans = 1ll;
        while (ex > 0) {
            if (ex & 1ll) ans = (ans * x) % mod;
            ex >>= 1ll;
            x = (x * x) % mod;
        }
        return ans;
    }
}

namespace io {

    istringstream _inp;
    string _inps;

    void common() {
        _inp.clear();
        _inps = "";
        _inp.str(_inps);
    }

    int gi() {
        int x;
        while (true) {
            try {
                while (_inp.peek() == ',' || _inp.peek() == ' ')
                    _inp.ignore();
                if (_inp >> x)
                    return x;
                else throw 6;
            } catch (...) {
                getline(cin, _inps);
                _inp.clear();
                _inp.str(_inps);
            }
        }
    }
}

#define BSET(a, p) ((a) | (1ll << (p)))
#define BCHK(a, p) (((a) & (1ll << (p)))>0)
#define BXOR(a, p) ((a) ^ (1ll << (p)));
#define BREM(a, p) (BCHK(a, p)?(BXOR(a, p)):(a))
#define BSHO(a, N) (bitset<N>(a))

#define fi first
#define sc second
#define pb push_back
#define X first
#define Y second


#ifdef DEBUG
#define dbg(s) {s;}
    bool debugging = true;
    #define PRELUDE {common();}
#endif

#ifndef DEBUG
#define dbg(s)
bool debugging = false;
#define PRELUDE { common(); ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define endl "\n"
#endif

#define i32 int32_t

#define RBTTYPE int
#define ordered_set tree<RBTTYPE, null_type, less<RBTTYPE>, rb_tree_tag,tree_order_statistics_node_update>
// Ordered set docs:
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

#define all(v) (v).begin(),(v).end()


using namespace io;
using namespace basics;


const int maxn = int(1e6 + 7);
const ll inf = ll(1e16 + 7);

const ld eps = 1e-7;
const ld pi = acosl(-1.0);


void hld_print(int, bool);
void start();
void finish();
void show_seg(vector<tuple<int,int,int>>);

vector < int > G[maxn];
int index_in_chain[maxn];
vector < int > chains[maxn];
int parent[maxn];
int sz[maxn];
int color[maxn];
int ht[maxn];
int max_ht;

/* void dfs_fns(int x, int pi, int h) { */
/*     parent[x] = pi; */
/*     sz[x] = 1; */
/*     ht[x] = h; */
/*     max_ht = max(max_ht, h); */
/*     for (int y : G[x]) { */
/*         if (y == pi) continue; */
/*         dfs_fns(y, x, h + 1); */
/*         sz[x] += sz[y]; */
/*     } */
/* } */

void dfs_fns(int x, int pi, int h) {
    parent[x] = pi;
    sz[x] = 1;
    ht[x] = h;

    max_ht = max(max_ht, h);

    for (int y : G[x]) {
        if (y == pi) continue;
        dfs_fns(y, x, h + 1);
        sz[x] += sz[y];
    }
}

/* void dfs_hld(int x, int pi) { */
/*     int best = -1; */
/*     for (int y : G[x]) { */
/*         if (y == pi) continue; */
/*         if (best < 0 || sz[y] > sz[best]) { */
/*             best = y; */
/*         } */
/*     } */ 
/*     if (best < 0) return; */
/*     color[best] = color[x]; */
/*     index_in_chain[best] = index_in_chain[x] + 1; */
/*     chains[color[x]].pb(best); */

/*     dfs_hld(best, x); */
/*     for (int y : G[x]) { */
/*         if (y == pi || y == best) continue; */
/*         color[y] = y; */
/*         index_in_chain[y] = 1; */
/*         chains[y].pb(y); */
/*         dfs_hld(y, x); */
/*     } */
/* } */

void dfs_hld(int x, int pi) {
    int best = -1;
    for (int y : G[x]) {
        if (y == pi) continue;
        if (best < 0 || sz[y] > sz[best]) {
            best = y;
        }
    }
    if (best < 0) return;
    color[best] = color[x];
    index_in_chain[best] = index_in_chain[x] + 1;
    chains[color[x]].pb(best);

    dfs_hld(best, x);

    for (int y : G[x]) {
        if (y == pi || y == best) continue;
        color[y] = y;
        index_in_chain[y] = 1;
        chains[y].pb(y);
        dfs_hld(y, x);
    }
}

/* int clk = 0; */


// all(x) = x.begin(), x.end()


/* vector < tuple<int, int, int> > segments(int x, int y) { */
/*     vector < tuple<int, int, int> > xseg = {}; */
/*     vector < tuple<int, int, int> > yseg = {}; */

/*     while (true) { */
/*         cerr << x << ", " << y << endl; */
/*         if (color[x] == color[y]) { */
/*             xseg.pb({color[x], index_in_chain[x], index_in_chain[y]}); */
/*             break; */
/*         } */

/*         if (ht[color[x]] < ht[color[y]]) { */
/*             yseg.pb({color[y], 1, index_in_chain[y]}); */
/*             yseg.pb({-1, parent[color[y]], color[y]}); */
/*             y = parent[color[y]]; */
/*         } else { */
/*             xseg.pb({color[x], index_in_chain[x], 1}); */
/*             xseg.pb({-1, color[x], parent[color[x]]}); */
/*             x = parent[color[x]]; */
/*         } */

/*     } */
    
/*     reverse(all(yseg)); */
/*     for (auto z : yseg) xseg.pb(z); */
/*     return xseg; */
/* } */

//               
// convention: {c, i, j}, {-1, u, v}

vector < tuple<int, int, int> > segments (int x, int y) {
    vector < tuple < int, int, int> > xseg = {};
    vector < tuple < int, int, int> > yseg = {};

    while (true) {
        if (color[x] == color[y]) {
            xseg.pb({color[x], index_in_chain[x], index_in_chain[y]});
            break;
        }

        if (ht[color[x]] < ht[color[y]]) {
            yseg.pb({color[y], 1, index_in_chain[y]}); // go to top of chain
            yseg.pb({-1, parent[color[y]], color[y]});
            y = parent[color[y]];
        } else {
            xseg.pb({color[x], index_in_chain[x], 1});
            xseg.pb({-1, color[x], parent[color[x]]});
            x = parent[color[x]];
        }
    }

    reverse(all(yseg));
    for (auto z : yseg) xseg.pb(z);
    return xseg;
}

/* void dfs_order(int x, int pi) { */
/*     clk++; */
/*     lft[x] = clk; */
/*     for (int y : G[x]) { */
/*         if (y == pi) continue; */
/*         dfs_order(y, x); */
/*     } */
/*     rgt[x] = clk; */
/* } */

int clk = 0;

int lft[maxn];
int rgt[maxn];


void dfs_order (int x, int pi) {
    clk++;
    lft[x] = clk;

    for (int y : G[x]) {
        if (y == pi) continue;
        dfs_order(y, x);
    }

    rgt[x] = clk;
}

int rand_bias(int); // ignore this function

void _main() {

    int n; cin >> n;
    for (int i = 2; i <= n; i++) {
        G[rand_bias(i)].pb(i);
    }
    
    /* dfs_order(1, -1); */
    


    dfs_fns(1, -1, 0);
   
    // initialize chains
    color[1] = 1;
    index_in_chain[1] = 1;
    chains[1].pb(1);

    // compute HLD

    dfs_hld(1, -1);
    
    

#define SEG

#ifdef SEG
    int a, b; cin >> a >> b;
    vector < tuple < int, int, int > > seg = segments(a, b);
#endif

    // ignore after this
    start();
    hld_print(n, false);

#ifdef SEG
    show_seg(seg);
#endif

    finish();
}

int rand_bias(int x) {
    return ri(x - 1) + 1;
}

i32 main() {

    PRELUDE;

    auto start = chrono::high_resolution_clock::now();
    _main();
    auto end = chrono::high_resolution_clock::now();
    auto dur = chrono::duration_cast<chrono::milliseconds>(end - start);

    if (debugging) {
        /* cout << "Time: " << dur.count() << " ms" << endl; */
    }
}

////////////////// IGNORE ////////////////////////

void OUT(string s) {
    cout << s << endl;
}

string gradient(double s) {
    /* return "black"; */
    s = 0.95 * s + 0.02;
    s = 1 - s;
    int b = floor(s * s * 156) + 100, g = floor(s / 2 * 156 + 100), r = floor((1 - s) * 156 + 100);
    return fmt::format("#{:x}{:x}{:x}", r, g, b);
}

string rand_color() {
    int r = ri(156) + 100, g = ri(156) + 100, b = ri(156) + 100;
    return fmt::format("#{:x}{:x}{:x}", r, g, b);
}

void start() {
    OUT("digraph {");
}

void finish() {
    OUT ("}");
}

void hld_print(int n, bool colht) {

    int* content = sz;
    int* grad = lft; int max_grad = n;
    
    map<int, string> gencolors;

    for (int i = 1; i <= n; i++) {
        int col = color[i];
        if (gencolors.count(col) == 0) {
            gencolors[col] = rand_color();
        }
        OUT(fmt::format("v{0} [label=\"{0} ({1}) \", fillcolor=\"{2}\", color = \"{3}\", style=filled, shape = circle, penwidth = 1 ];", 
                    to_string(i), 
                    colht ? to_string(lft[i]) : to_string(content[i]), 
                    colht ? gradient(1.0 * grad[i] / max_grad) : gencolors[col], 
                    colht ? gencolors[col] : gradient(1.0 * grad[i] / max_grad)
                ));
    }

    for (int i = 1; i <= n; i++) {
        for (int y : G[i]) {
            OUT(fmt::format("v{0} -> v{1}[color = \"{2}\", penwidth={3}];", 
                        to_string(i), to_string(y), 
                        (color[i] == color[y]) ? gencolors[color[i]] : "#AAAAAA",
                        (color[i] == color[y]) ? "5" : "2"));
        }
    }
}

void show_seg (vector <tuple<int, int, int> > seg) {
    for (auto z : seg) {
        int c, x, y; tie(c, x, y) = z;
        cerr << c << ", " << x << " -- " << y << endl;
        if (c >= 0) x = chains[c][x - 1], y = chains[c][y - 1];
        OUT(fmt::format("v{0} -> v{1}[color=black, penwidth = 6];", to_string(x), to_string(y)));
    }
}

Makefile

compile:
	pkg-config fmt
	g++ --std=c++17 code.cc -lfmt

run: compile
	./a.out > out.dot
	dot -Tpng -Nfontname=Google\ Sans out.dot > out.png

disp:
	firefox out.png