#include <bits/stdc++.h> //#define int long long ...

Question

#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using i128 = __int128_t;

const int N = 1e8 + 7;
const int L = 20;
const int C = 320;
const int B = 128;

struct node {
int sz, par;
};

void solve() {
int n, m, start, finish;
cin >> n >> m >> start >> finish;
n++;

vector< vector< int > > g(n);
vector< node > d(n);

while (m--) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
function< void(int, int, int) > dfs = [&](int v, int p, int sz) {
d[v].sz = sz;
d[v].par = p;
if (p == -1) d[v].par = v;

text
for (auto u : g[v]) {
  if (u == p) continue;

  dfs(u, v, sz + 1);
}

};

dfs(rand() % n, -1, 0);

vector< vector< int > > jm(n, vector< int > (L));
for (int v = 0; v < n; v++) {
jm[v][0] = d[v].par;
}

for (int k = 1; k < L; k++) {
for (int v = 0; v < n; v++) {
jm[v][k] = jm[jm[v][k - 1]][k - 1];
}
}

if (d[start].sz < d[finish].sz) swap(start, finish);
int dv = start , du = finish;
for (int k = L - 1; k >= 0; k--) {
int dv1 = jm[dv][k];
if (d[dv1].sz >= d[du].sz) dv = dv1;
}

if (dv == du) {
cout << d[start].sz - d[finish].sz;
return;
}

for (int k = L - 1; k >= 0; k--) {
int dv1 = jm[dv][k], du1 = jm[du][k];

text
if (dv1 != du1) {
  dv = dv1; du = du1;
}

}
cout << d[start].sz + d[finish].sz - 2 * d[d[dv].par].sz;
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}
return 0;
}

вершины от 0 = до n
это норм реализация или можно сильно легче?

Answer 1

Есть несколько проблем.

n++ делает вершины 0..n, но потом dfs(rand() % n, ...) выбирает только 0..n-1, вершина n никогда не станет корнем.
Если граф дерево на вершинах 0..n, то рёбер должно быть n, а не n-1; зависит от условия.
DFS без visited зациклится, если граф не дерево.
L = 20 мало для 1e8, нужно хотя бы 27–30.
Рандомный корень не нужен и опасен для несвязного графа.
Для одного запроса расстояния LCA — сильно избыточно.

Если нужен один путь/расстояние между start и finish в невзвешенном графе/дереве, проще BFS:

cpp
void solve() {
    int n, m, start, finish;
    cin >> n >> m >> start >> finish;

    // вершины 0..n
    vector<vector<int>> g(n + 1);

    while (m--) {
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
        g[u].push_back(v);
    }

    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        if (v == finish) break;

        for (int u : g[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    cout << dist[finish];
}

Если граф точно дерево, можно даже DFS от start до finish, но BFS надёжнее и короче.

LCA имеет смысл, если запросов расстояния много: например q запросов после одного препроцессинга.

Answer 2

Для самого бинарного подъёма идея нормальная, но реализацию можно сделать чище и безопаснее.

Главные замечания:

cpp
const int L = 20;

мало, если n может быть больше 2^20. Лучше так:

cpp
int LOG = 1;
while ((1 << LOG) <= n) LOG++;

И rand() как корень лучше убрать:

cpp
dfs(0, 0, 0); // или любой гарантированно существующий корень

Более чистая версия LCA:

cpp
int LOG = 1;
while ((1 << LOG) <= n) LOG++;

vector<int> depth(n);
vector<vector<int>> up(LOG, vector<int>(n));

function<void(int, int)> dfs = [&](int v, int p) {
    up[0][v] = p;

    for (int k = 1; k < LOG; k++) {
        up[k][v] = up[k - 1][up[k - 1][v]];
    }

    for (int u : g[v]) {
        if (u == p) continue;
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
};

dfs(root, root);

auto jump = [&](int v, int dist) {
    for (int k = 0; k < LOG; k++) {
        if (dist & (1 << k)) {
            v = up[k][v];
        }
    }
    return v;
};

auto lca = [&](int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    a = jump(a, depth[a] - depth[b]);

    if (a == b) return a;

    for (int k = LOG - 1; k >= 0; k--) {
        if (up[k][a] != up[k][b]) {
            a = up[k][a];
            b = up[k][b];
        }
    }

    return up[0][a];
};

Расстояние:

cpp
int c = lca(start, finish);
cout << depth[start] + depth[finish] - 2 * depth[c];

То есть твоя реализация в целом рабочая для дерева, но я бы упростил так:

depth вместо sz, потому что это глубина, не размер;
up[k][v], а не jm[v][k], обычно так удобнее;
LOG считать от n;
предков заполнять прямо в DFS;
вынести jump() и lca() отдельно.

#include <bits/stdc++.h> //#define int long long ...

प्रश्न

उत्तर

प्रश्न

उत्तर

इस प्रश्नोत्तर को साझा करें