Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement