@soulfriend
с++

Можете решать эту задачу?

Сама задача на Английском(
Initially you are given a tree consisting of only one root (the vertex with the number 1). You need to answer the following queries:

ADD a b - hang the vertex b under the vertex a (it is guaranteed that the vertex a already exists).
GET a b - return the LCA of vertices a and b.
The vertices are numbered from 1 to n. At each moment of time you have only one tree.

Input
The first line contains the number of queries k. Next k lines contains the queries. There is no more than 500000 queries of each type.

Output
For each query of type GET print in separate line one integer - the answer to the corresponding query.

Example
Input:
9
ADD 1 2
ADD 1 3
ADD 2 4
GET 1 3
GET 2 3
GET 3 4
ADD 2 5
GET 4 5
GET 5 5


Output:
1
1
1
2
5


это мой код
но не прошел все тесты
#include <bits/stdc++.h>
 
using namespace std;
const long long inf = 1ll<<50;
vector<int> g[100100];
const int L = 20;
const int maxn = 100100;
int p[L][maxn];
int tin[maxn];
int tout[maxn];
int lev[maxn];
int timer = 0;
void dfs(int v, int pa) {
    lev[v] = lev[pa] + 1;
    tin[v] = timer;
    timer++;
    p[0][v] = pa;
    for(int i = 1; i < L; i++) {
        p[i][v]= p[i-1][p[i-1][v]];
    }
    for(int to: g[v]) {
        if(to != pa) {
            dfs(to, v);
        }
    }
    tout[v] = timer-1;
}
int parent(int u, int v) {
    if(tin[u] <= tin[v] && tout[u] >= tout[v]) {
        return 1;
    }
    return 0;
}
int lca(int u, int v) {
    if(parent(u, v)) {
        return u;
    }
    if(parent(v, u)) {
        return v;
    }
    for(int i = L-1; i >= 0; i--) {
        if(p[i][v] != 0 && !parent(p[i][v], u)) {
            v = p[i][v];
        }
    }
    return p[0][v];
}
int lca2(int u, int v) {
    if(lev[u] < lev[v]) {
        swap(u, v);
    }
    for(int i = L - 1; i >= 0; i--) {
        if(lev[u] - (1<<i) >= lev[v]) {
            u = p[i][u];
        }
    }
    if(u == v) return u;
    for(int i = L-1; i >= 0; i--) {
        if(p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
    }
    return p[0][v];
}
 
int main() {
    int n;
    cin >> n;
    for(int i= 0;i<n;i++) {
        string s;
        int a,b;
        cin>>s>>a>>b;
        if(s=="ADD") {
            g[a].push_back(b);
            g[b].push_back(a);
        }
        else {
            cout<<lca(a,b)<<endl;
        }
        dfs(1,0);
    }
}
  • Вопрос задан
  • 194 просмотра
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Можно забить на добавление вершин. Поскольку в задаче нет команд "удалить вершину" и гаранитируется, что в каждый момент времени структура будет деревом, то можно просто сначала создать дерево из всех вершин, и потом в нем выполнить все LCA.

Воспользуйтесь алгоритмом тарьяна: https://e-maxx.ru/algo/lca_linear_offline для получения ответов на все запросы LCA сразу.

Сначала при вводе создайте дерево целиком и запомните все запросы Get в массив. Потом пройдитесь по массиву запросов и раскидайте их в списки на вершинах, как надо в алгоритме таръяна.

Вам надо лишь чуть-чуть подкорректировать этот код, чтобы вместе с вершиной-запросом добавлять в списки к вершинам номер этого запроса. И тогда вместо вывода v+1, q[v][i]+1 вы сможете записать ответ в массив по нужному индексу.

Ну или воспользуйтесь онлайн алгоритмом для поиска LCA через обход со временем входа/выхода и деревом отрезков на минимимум.
Ответ написан
Комментировать
@Mercury13
Программист на «си с крестами» и не только
Изначально:
1. У корня глубина 0.

Команда ADD:
1. вершина.предок = предок
2. вершина.глубина = предок.глубина + 1

Команда GET:
1. Найти ту вершину, что глубже. Если у одной глубина 5, у другой 7 — подняться от второй на 2.
2. А теперь параллельно и от первой, и от второй вершины поднимаемся вверх на единицу, пока не придём в одну и ту же вершину.

Если хватит памяти — можно устроить какой-то кэш. Мой вариант — кэшировать предков порядка 1,2,4,8…
Чтобы подняться от вершины на 30 единиц…
1. Находим ближайшую степень двойки (16).
2. Если эта степень есть в кэше — просто берём её.
3. Иначе находим максимальную имеющуюся степень (например, 4). Заходим в эту вершину и рекурсивно поднимаемся от неё на 4, потом на 8, заполняя наш кэш.
4. На оставшиеся 14 поднимаемся по тому же алгоритму.

Чтобы найти общего предка двух вершин — у одной глубина 30, у другой 40.
1. От той вершины, у которой 40, поднимаемся на 10 единиц. Алгоритм я привёл.
2. Одинаковые? — тогда понятно.
3. Имеют общего предка? — тогда понятно.
4. Иначе поднимаемся на 1, 2, 4, 8, 16 единиц от каждой из них по указанному алгоритму, каждый из этих шагов при наличии кэша даст O(1). Находим последнюю НЕСОВПАДАЮЩУЮ глубину. Для них повторяем алгоритм.

ВАРИАНТ КЭША ВТОРОЙ. Для вершины глубины 27=11010 кэшировать предков АБСОЛЮТНЫХ (то есть от корня!) глубин 16=1.0000, 24=11.000, 24 :) =110.00, 26=1101.0. Тогда при создании вершины весь кэш достаточно быстро строится на основе кэша вершины-предка.

Чтобы подняться от вершины глубины 27 на расстояние, например, 5, нам нужна абсолютная глубина 27−5=22.
Есть только 24 → действуем так. Выныриваем туда на 24, но там кэш совершенно негодный → а дальше нас проведёт кэш глубины 23. Так поднимаемся на 1 до 23-й и повторяем алгоритм.

Чтобы найти общего предка двух вершин (их глубины, скажем, 27 и 42), точно так же уравниваем глубины. Затем поднимаемся до глубин 16, 24, 24, 26…, пока не найдём несовпадение. Идём в эти несовпадающие вершины, проходим от них к предку и повторяем алгоритм.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы