CCO Training Contest 4 Three Nodes

#include <bits/stdc++.h>
#include <chrono>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
using namespace chrono;

mt19937 rnd(steady_clock::now().time_since_epoch().count());

const int N = 3e5 + 128;
const int LOG = 18;
vector <int> g[N];
int n;
int dp[N]; // limit.
int h[N], vert[N];
int tin[N], tout[N];
int timer;
int nxt[N][LOG];
int lift[N][LOG];
int to[N][3];
int upv[N], dir[N];
int ans[N][3];
int x[N], y[N], z[N];
pair <int, int> sum[4 * N];
int add[4 * N];

void bld(int v, int tl, int tr) {
    if (tl == tr) {
        sum[v] = make_pair(h[vert[tl]], vert[tl]);
        return;
    }
    int tm = (tl + tr) >> 1;
    bld(v << 1, tl, tm);
    bld(v << 1 | 1, tm + 1, tr);
    sum[v] = max(sum[v << 1], sum[v << 1 | 1]);
}

void apply(int v, int tl, int tr, int x) {
    sum[v].first += x;
    add[v] += x;
}

void push(int v, int tl, int tr) {
    if (add[v] == 0)
        return;
    int tm = (tl + tr) >> 1;
    apply(v << 1, tl, tm, add[v]);
    apply(v << 1 | 1, tm + 1, tr, add[v]);
    add[v] = 0;
}

void update(int l, int r, int x, int v, int tl, int tr) {
    if (tl > r || tr < l)
        return;
    push(v, tl, tr);
    if (l <= tl && tr <= r) {
        apply(v, tl, tr, x);
        return;
    }
    int tm = (tl + tr) >> 1;
    update(l, r, x, v << 1, tl, tm);
    update(l, r, x, v << 1 | 1, tm + 1, tr);
    sum[v] = max(sum[v << 1], sum[v << 1 | 1]);
}

pair <int, int> get_max(int l, int r, int v, int tl, int tr) {
    if (tl > r || tr < l)
        return make_pair(-1, -1);
    push(v, tl, tr);
    if (l <= tl && tr <= r)
        return sum[v];
    int tm = (tl + tr) >> 1;
    return max(get_max(l, r, v << 1, tl, tm),
                get_max(l, r, v << 1 | 1, tm + 1, tr));
}

vector < pair<int, int> > C[N];

struct max_path {
    int max_dist, pt;
    bool iup;

    max_path() {
        max_dist = 0;
        pt = -1;
        iup = false;
    }
};

struct st {
    vector <max_path> cur;

    int v;

    bool operator < (const st& other) const {
        assert((int)cur.size() == (int)other.cur.size());
        for (int c = 0; c < 3; c++)
            if (cur[c].max_dist != other.cur[c].max_dist)
                return cur[c].max_dist < other.cur[c].max_dist;
        return v < other.v;
    };

    st() {
        cur.clear();
        v = -1;
    }
};

int get(int v, int k) {
    for (int b = 0; b < LOG; b++)
        if ((k >> b) & 1)
            v = lift[v][b];
    return v;
}

int get_lca(int u, int v) {
    if (h[v] > h[u])
        swap(u, v);
    int k = h[u] - h[v];
    u = get(u, k);
    if (u == v)
        return u;
    for (int b = LOG - 1; b >= 0; b--)
        if (lift[v][b] != lift[u][b])
            v = lift[v][b], u = lift[u][b];
    return lift[v][0];
}

int get_dist(int u, int v) {
    return h[u] + h[v] - 2 * h[get_lca(u, v)];
}

vector < st > options;

void dfs(int v, int p = 1) {
    if (v != 1)
        h[v] = h[p] + 1;

    tin[v] = timer++;
    vert[tin[v]] = v;

    lift[v][0] = p;
    for (int b = 1; b < LOG; b++)
        lift[v][b] = lift[lift[v][b - 1]][b - 1];

    for (auto& to : g[v])
        if (to != p)
            dfs(to, v);

    tout[v] = timer - 1;
}

void go(int v, int p = -1) {
    vector < pair<int, int> >  values;
    for (auto& to : g[v])
        if (to != p) {
            values.push_back(get_max(tin[to], tout[to], 1, 0, n - 1));
            update(0, n - 1, +1, 1, 0, n - 1);
            update(tin[to], tout[to], -2, 1, 0, n - 1);
            go(to, v);
            update(0, n - 1, -1, 1, 0, n - 1);
            update(tin[to], tout[to], +2, 1, 0, n - 1);
        }

    if (tin[v] > 0)
        values.push_back(get_max(0, tin[v] - 1, 1, 0, n - 1));
    if (tout[v] + 1 < n)
        values.push_back(get_max(tout[v] + 1, n - 1, 1, 0, n - 1));

    sort(rall(values));

    st x;
    x.v = v;

    bool was_up = false;
    for (auto& [dist, vertex] : values) {
        if ((int)x.cur.size() == 3)
            break;
        bool needUp = (get_lca(vertex, v) != v);
        if (needUp && was_up)
            continue;
        max_path maxi;
        if (needUp) {
            was_up = true;
            maxi.iup = true;
        } else {
            if (!nxt[v][0])
                nxt[v][0] = get(vertex, h[vertex] - h[v] - 1);
        }
        maxi.max_dist = dist;
        maxi.pt = vertex;
        x.cur.push_back(maxi);
    }

    options.push_back(x);
}

pair <int, int> mx[4 * N];

void build(int v, int tl, int tr) {
    mx[v] = make_pair(-1, -1);
    if (tl == tr)
        return;
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build(v << 1 | 1, tm + 1, tr);
}

void update(int pos, pair<int, int> val, int v, int tl, int tr) {
    if (tl > pos || tr < pos)
        return;
    if (tl == tr) {
        mx[v] = max(mx[v], val);
        return;
    }
    int tm = (tl + tr) >> 1;
    update(pos, val, v << 1, tl, tm);
    update(pos, val, v << 1 | 1, tm + 1, tr);
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}

pair <int, int> get(int l, int r, int v, int tl, int tr) {
    if (tl > r || tr < l)
        return make_pair(-1, -1);
    if (l <= tl && tr <= r)
        return mx[v];
    int tm = (tl + tr) >> 1;
    return max(get(l, r, v << 1, tl, tm),
                get(l, r, v << 1 | 1, tm + 1, tr));
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u = i + 1, v = rnd() % i + 1;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);

    bld(1, 0, n - 1);

    go(1);

    sort(all(options), [&](const auto& x, const auto& y) -> bool {
        return x.v < y.v;
    });

    for (int b = 1; b < LOG; b++)
        for (int v = 1; v <= n; v++)
            nxt[v][b] = nxt[nxt[v][b - 1]][b - 1];

    for (auto& x : options)
        while ((int)x.cur.size() < 3)
            x.cur.push_back(max_path());

    sort(rall(options));

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        cin >> x[i] >> y[i] >> z[i];
        assert((x[i] + y[i] - z[i]) % 2 == 0);
        C[i].push_back(make_pair((x[i] + y[i] - z[i]) / 2, 0));
        assert((x[i] - y[i] + z[i]) % 2 == 0);
        C[i].push_back(make_pair((x[i] - y[i] + z[i]) / 2, 1));
        assert((y[i] + z[i] - x[i]) % 2 == 0);
        C[i].push_back(make_pair((y[i] + z[i] - x[i]) / 2, 2));

        sort(rall(C[i]));
    }

    vector <int> order(q);
    iota(all(order), 0);

    sort(all(order), [&](const int& x, const int& y) -> bool {
        for (int c = 0; c < 3; c++)
            if (C[x][c].first != C[y][c].first)
                return C[x][c].first > C[y][c].first;
        return x < y;
    });

    int p0 = -1;

    build(1, 0, N);

    for (int c = 0; c < q; c++) {
        int v = order[c];
        while (p0 + 1 < n && options[p0 + 1].cur[0].max_dist >= C[v][0].first) {
            ++p0;
            update(options[p0].cur[1].max_dist, make_pair(options[p0].cur[2].max_dist, p0), 1, 0, N);
        }

        auto [value, pos] = get(C[v][1].first, N, 1, 0, N);
        assert(value >= C[v][2].first);

        for (int c = 0; c < 3; c++) {
            auto [dist, ix] = C[v][c];

            if (dist == 0) {
                ans[v][ix] = options[pos].v;
                continue;
            }

            if (options[pos].cur[c].iup) {
                int x = get_lca(options[pos].v, options[pos].cur[c].pt);
                if (dist <= h[options[pos].v] - h[x]) {
                    ans[v][ix] = get(options[pos].v, dist);
                } else {
                    dist -= h[options[pos].v] - h[x];
                    int tx = get(options[pos].cur[c].pt, h[options[pos].cur[c].pt] - h[x] - 1);
                    dist--;
                    for (int b = 0; b < LOG; b++)
                        if ((dist >> b) & 1)
                            tx = nxt[tx][b];
                    ans[v][ix] = tx;
                }
            } else {
                int tx = get(options[pos].cur[c].pt, h[options[pos].cur[c].pt] - h[options[pos].v] - 1);
                dist--;
                for (int b = 0; b < LOG; b++)
                    if ((dist >> b) & 1)
                        tx = nxt[tx][b];
                ans[v][ix] = tx;
            }
        }
    }

    for (int i = 0; i < q; i++)
        for (int c = 0; c < 3; c++)
            cout << ans[i][c] << " \n"[c + 1 == 3];

}

main() {
    boost;
    solve();
    return 0;
}