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

Question

[jandos jumahanov]

Сама задача на Английском(
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);
    }
}

Comments

[Wataru]

*sorry, i don't really know english

Тут можно и по русски спрашивать. Or do you not speak russian?

[mayton2019]

До он издевается. Хочет чтобы читающие в уме нарисовали дерево. Неужели нельзя было приаттачить картинку с деревом?

[jandos jumahanov]

Wataru, ок хорошо

[jandos jumahanov]

mayton2019, простите. Если кто то решил эту задачу то могут ли они помочь мне?

[mayton2019]

jandos jumahanov, твой код - грязноват. Зачем нужна функция lca2 ?

А это зачем?

vector<int> g[100100];

Сто тысяч векторов. Это чтоб точно-точно хватило?

Answer 1

[Wataru]

Можно забить на добавление вершин. Поскольку в задаче нет команд "удалить вершину" и гаранитируется, что в каждый момент времени структура будет деревом, то можно просто сначала создать дерево из всех вершин, и потом в нем выполнить все LCA.

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

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

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

Ну или воспользуйтесь онлайн алгоритмом для поиска LCA через обход со временем входа/выхода и деревом отрезков на минимимум.

Answer 2

[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…, пока не найдём несовпадение. Идём в эти несовпадающие вершины, проходим от них к предку и повторяем алгоритм.

Comments

[Wataru]

Это будет медленно и почти наверняка не пройдет по времени. Это же олимпиадная задача. Кстати, автор примерно так уже и делает, только с логарифмическим поднятием вверх.

[Mercury13]

Wataru, Я тут расписал свой пример кэширования.

[Mercury13]

Wataru, Этот мэн с каждым шагом делает DFS — точно не пройдёт.

[Wataru]

Mercury13, Это да. Надо в этой задаче забить на добавление вершин по одной и просто сразу добавить их все. А дальше у автора уже ровно как у вас расписано кэш и работает для этого массив p используется.

[Mercury13]

Wataru, У автора DFS каждый шаг, и это точно негодно.

[mayton2019]

В процессе поиска общего предка надо завести по 2 хеш-сета. И двигаясь наверх на каждой итерации - просто добавлять по одному предку и проверять соседний хеш-сет на contains.

Если какой-то текущий потомок-кандидат поднялся до уровня корня - то алгоритм останавливается. Искать больше нечего.

По объемам. Пишут что 500000. Дерево - неизвестного типа. Не бинарное. Тоеть в вырожденном случае это 1 корень и 499999 детей. И в другом вырожденном случае - это цепочка длиной 500 тыщ. Но в каком-то среднем жлобском случае - это (грубо) логарифм по основанию 2 + хвостик == 18 (грубо).

Тоесть 18 добавлений в хеш-сеты и 18 проверок по хеш-сетам нас отделяют от победы.

[Mercury13]

mayton2019, Зачем хэши — достаточно встать на одну глубину, а потом синхронно подниматься.

[Mercury13]

mayton2019, А если сделали два хлыста по 250к, а затем в этих хлыстах 500к раз ищут общих родителей — хэши никак не ускорят, всё равно O(n).

[mayton2019]

Mercury13, ну тут варианты. Если дерево вытянутое. То нам надо для расчета высоты - пробежать 500 тыщ. Тоесть мы выходим на O(n)

[Mercury13]

mayton2019, С учётом количества запросов — O(n²). Time limit.