Разбор Codeforces Round 973 (Div. 2)
Разница между ru25 и ru26, 6 символ(ов) изменены
[2013A — Блендер Жана](https://mirror.codeforces.com/contest/2013/problem/A)↵

Первый решивший: [user:rob00,2024-09-21]↵

<spoiler summary="Разбор">↵
Давайте рассмотрим $2$ случая.↵

- Если $x \geq y$. В этом случае, каждую секунду блендер будет смешивать $min(y, c)$ фруктов (где $c$ &mdash; это количество не смешанных фруктов). Cледовательно, ответ будет $\lceil {\frac{n}{y}} \rceil$.↵
- Если $x < y$. Здесь каждую секунду блендер будет смешивать $min(x, c)$ фруктов. В этом случае ответ будет равен $\lceil {\frac{n}{x}} \rceil$ аналогично.↵

Таким образом, итоговый ответ — это $\lceil {\frac{n}{min(x, y)}} \rceil$. ↵
</spoiler>↵

<spoiler summary="Решение">↵
```↵
#include <iostream>↵

using namespace std;↵

int main(){↵
    int t = 1;↵
    cin >> t;↵
    while(t--){↵
        int n, x, y;↵
        cin >> n >> x >> y;↵
        x = min(x, y);↵
        cout << (n + x - 1) / x << endl;↵
    }↵
}↵

```↵
</spoiler>↵

[2013B &mdash; Бой на выживание](https://mirror.codeforces.com/contest/2013/problem/B)↵

Первый решивший: [user:neal,2024-09-21]↵

<spoiler summary="Разбор">↵
Можно заметить, что значение $a_{n-1}$ всегда будет отрицательным в итоговом ответе.↵

Следовательно, мы можем вычесть сумму $a_1 + a_2 + \ldots + a_{n-2}$ из $a_{n-1}$, а затем вычесть $a_{n-1}$ из $a_n$.↵

Таким образом, итоговая сумма будет равна $a_1 + a_2 + \ldots + a_{n-2} - a_{n-1} + a_n$. Больше этого значения получить нельзя, так как $a_{n-1}$ всегда будет отрицательным.↵
</spoiler>↵

<spoiler summary="Решение">↵
```↵
#include <bits/stdc++.h>↵
 ↵
using namespace std;↵
typedef long long ll;↵
 ↵
const int mod = 1e9 + 7;↵
 ↵
void solve(){↵
    int n;↵
    cin >> n;↵
    ll ans = 0;↵
    vector<int> a(n);↵
    for(int i=0;i<n;i++){↵
        cin >> a[i];↵
        ans += a[i];↵
    }↵
    cout << ans - 2 * a[n - 2] << '\n';↵
}↵
 ↵
int main(){↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    int t;↵
    cin >> t;↵
    while(t--){↵
        solve();↵
    }↵
}↵
```↵
</spoiler>↵

[2013C &mdash; Взлом Пароля](https://mirror.codeforces.com/contest/2013/problem/C)↵

Первый решивший: [user:Pagode_Paiva,2024-09-21]↵

<spoiler summary="Разбор">↵
Будем поддерживать изначально пустую строку $t$, так чтобы $t$ встречалась в $s$ как подстрока.↵

Будем увеличивать строку $t$ на один символ, пока её длина меньше $n$.↵

Проведём $n$ итераций. На каждой из них будем проверять строки $t + 0$ и $t + 1$. Если одна из них встречается в $s$ как подстрока, то добавим нужный символ в конец $t$ и перейдём к следующей итерации.↵

Если ни одна из этих двух строк не встречается в $s$, то это значит, что строка $t$ является суффиксом строки $s$. После этой итерации будем проверять строку $0 + t$. Если она встречается в $s$, то добавим $0$ к $t$, иначе добавим $1$.↵

Итого, на каждой итерации мы выполняем по 2 запроса, кроме одной итерации, на которой выполняем 3 запроса. Однако после этой итерации будем делать только по 1 запросу, поэтому суммарно потребуется не более $2 \cdot n$ запросов.↵
</spoiler>↵

<spoiler summary="Решение">↵
```↵

#include <iostream>↵
#include <vector>↵
#include <string>↵
#include <array>↵
 ↵
using namespace std;↵
 ↵
bool ask(string t) {↵
    cout << "? " << t << endl;↵
    int res;↵
    cin >> res;↵
    return res;↵
}↵
 ↵
void result(string s) {↵
    cout << "! " << s << endl;↵
}↵
 ↵
void solve() {↵
    int n;↵
    cin >> n;↵
    string cur;↵
    while (cur.size() < n) {↵
        if (ask(cur + "0")) {↵
            cur += "0";↵
        } else if (ask(cur + "1")) {↵
            cur += "1";↵
        } else {↵
            break;↵
        }↵
    }↵
    while ((int) cur.size() < n) {↵
        if (ask("0" + cur)) {↵
            cur = "0" + cur;↵
        } else{↵
            cur = "1" + cur;↵
        }↵
    }↵
    result(cur);↵
}↵
 ↵
int main() {↵
    int t;↵
    cin >> t;↵
    while (t--)↵
        solve();↵
}↵
```↵
</spoiler>↵

[2013D &mdash; Минимизировать разность](https://mirror.codeforces.com/contest/2013/problem/D)↵

Первый решивший: [user:edogawa_something,2024-09-21]↵

<spoiler summary="Разбор">↵

Первое утверждение: если $a_i > a_{i+1}$, то в этом случае всегда выгодно сделать операцию на позиции $i$. Следовательно, конечный массив будет неубывающим.↵

Второе утверждение: если массив неубывающий, то делать операции невыгодно.↵

Будем поддерживать стек, в котором будет храниться отсортированный массив. Каждый элемент в стеке будет представлять пару $x, cnt$, где $x$ — значение, а $cnt$ — количество его вхождений.↵

При добавлении $a_i$ в стек будем хранить сумму удалённых элементов $sum$ из стека и их количество $cnt$. Изначально $sum = a_i$, $cnt = 1$. Мы будем удалять последний элемент из стека, пока он 
менбольше, чем $ \frac{sum}{cnt}$. После этого пересчитываем $sum$ и $cnt$. Затем добавим в стек пары $\left( \frac{sum}{cnt}, cnt - sum \mod cnt \right)$ и $\left( \frac{sum}{cnt} + 1, sum \mod cnt \right) $.↵

Временная сложность алгоритма — $O(n)$, так как на каждой итерации добавляется не более 2 элементов в стек, и каждый элемент удаляется не более одного раза.↵
</spoiler>↵

<spoiler summary="Решение">↵
```↵
#include <bits/stdc++.h>↵

using namespace std;↵
typedef long long ll;↵

ll a[200200];↵
int n;↵

void solve(){↵
    cin >> n;↵
    for(int i=1;i<=n;i++){↵
        cin >> a[i];↵
    }↵
    stack<pair<ll, int>> s;↵
    for(int i=1;i<=n;i++){↵
        ll sum = a[i], cnt = 1;↵
        while(s.size() && s.top().first >= sum / cnt){↵
            sum += s.top().first * s.top().second;↵
            cnt += s.top().second;↵
            s.pop();↵
        }↵
        s.push({sum / cnt, cnt - sum % cnt});↵
        if(sum % cnt != 0){↵
            s.push({sum / cnt + 1, sum % cnt});↵
        }↵
    }↵
    ll mx = s.top().first;↵
    while(s.size() > 1){↵
        s.pop();↵
    }↵
    cout << mx - s.top().first << '\n';↵
}↵

int main(){↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    int t = 1;↵
    cin >> t;↵
    while(t--){↵
        solve();↵
    }↵
}↵
```↵
</spoiler>↵

[2013E &mdash; Префиксные НОД](https://mirror.codeforces.com/contest/2013/problem/E)↵

Первый решивший: [user:meme,2024-09-21]↵

<spoiler summary="Разбор">↵

Пусть $g$ — наибольший общий делитель массива $a$. Поделим каждый элемент $a_i$ на $g$, а в конце просто умножим результат на $g$.↵

Рассмотрим следующий жадный алгоритм. Создадим изначально пустой массив $b$ и будем добавлять в конец массива $b$ элемент, который минимизирует НОД с уже имеющимся массивом $b$. Можно заметить, что НОД через максимум 10 итераций станет равным 1. После этого можно в любом порядке добавить оставшиеся элементы.↵

<spoiler summary="Доказательство">↵
Пусть $A$ — это минимально возможный НОД для текущего префикса массива $b$, а $B$ — оптимальный ответ, такой что $A < B$. Тогда мы можем сначала поставить $A$, а затем записать последовательность $B$, в том же порядке. Ответ не ухудшится, так как $A + gcd(A, B) \leq B$.↵
</spoiler>↵

Временная сложность алгоритма: $O(n \cdot 10)$.↵
</spoiler>↵

<spoiler summary="Решение">↵
```↵
#include <bits/stdc++.h>↵

using namespace std;↵

int a[200200];↵
int n;↵

void solve(){↵
    cin >> n;↵
    int g = 0, cur = 0;↵
    long long ans = 0;↵
    for(int i=0;i<n;i++){↵
        cin >> a[i];↵
        g = __gcd(g, a[i]);↵
    }↵
    for(int i=0;i<n;i++){↵
        a[i] /= g;↵
    }↵
    for(int t=0;t<n;t++){↵
        int nc = 1e9;↵
        for(int i=0;i<n;i++){↵
            nc = min(nc, __gcd(cur, a[i]));↵
        }↵
        cur = nc;↵
        ans += cur;↵
        if(cur == 1) {↵
            ans += n - t - 1;↵
            break;↵
        }↵
    }↵
    cout << ans * g << '\n';↵
}↵

int main(){↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    int t = 1;↵
     cin >> t;↵
    while(t--){↵
        solve();↵
    }↵
}↵
```↵
</spoiler>↵

[2013F1 &mdash; Игра на дереве (простая версия)](https://mirror.codeforces.com/contest/2013/problem/F1)↵

Первый решивший: [user:EnofTaiPeople,2024-09-21]↵

<spoiler summary="Разбор">↵
Сначала разберём, как будет проходить игра. Алиса и Боб начинают двигаться друг к другу по пути от вершины $1$ к вершине $u$. В какой-то момент один из игроков может свернуть в поддерево вершины, которая не лежит на пути $(1, u)$. После этого оба игрока идут в самую дальнюю доступную вершину.↵

Пусть путь от вершины $1$ до вершины $u$ обозначается как $(p_1, p_2, \dots, p_m)$, где $p_1 = 1$ и $p_m = u$. Изначально Алиса стоит в вершине $p_1$, а Боб — в вершине $p_m$.↵

Для каждой вершины на пути $(p_1, p_2, \dots, p_m)$ введём два значения:↵

- $a_i$ — это количество вершин, которые посетит Алиса, если она спустится в поддерево вершины $p_i$, которое не лежит на пути $(1, u)$;↵

- $b_i$ — это количество вершин, которые посетит Боб, если он спустится в поддерево вершины $p_i$, которое также не лежит на этом пути.↵

Обозначим расстояние до самой дальней вершины в поддереве вершины $p_i$ как $d_{p_i}$. Тогда:↵

- $a_i = d_{p_i} + i$ — количество вершин, которые Алиса может посетить, если она спустится в поддерево на вершине $p_i$;↵

- $b_i = d_{p_i} + m - i + 1$ — количество вершин, которые Боб может посетить, если он спустится в поддерево на вершине $p_i $.↵

Теперь рассмотрим, что происходит, если Алиса стоит на вершине $p_i$, а Боб на вершине $p_j$. Если Алиса решит спуститься в поддерево вершины $p_i$, то она посетит $a_i$ вершин. В это время Боб может дойти до любой вершины на подотрезке $(p_i, p_{i+1}, \dots, p_j)$. Бобу выгодно спуститься в поддерево на вершине с максимальным значением $b_k$, где $k \in [i+1, j] $.↵

Следовательно, Алисе выгодно спуститься в поддерево вершины $p_i$, если выполняется условие:↵
$a_i > \max(b_{i+1}, b_{i+2}, \dots, b_j)$↵
Иначе она должна перейти на вершину $p_{i+1}$.↵

Для Боба ситуация аналогична: он спускается в поддерево вершины $p_j$, если для него выполняется условие, аналогичное условию для Алисы.↵

Для того чтобы эффективно находить максимум на подотрезке $(p_{i+1}, \dots, p_j)$, можно использовать дерево отрезков или разреженную таблицу. Это позволяет находить максимум за $O(log n)$ для каждого запроса, что даёт общую временную сложность  $O(nlog n)$.↵

Однако можно доказать, что вместо использования дерева отрезков или разреженной таблицы можно просто пробегаться по всем вершинам на подотрезке и завершать цикл при нахождении большей вершины. Это даст решение с временной сложностью $O(n)$.↵
</spoiler>↵

<spoiler summary="Решение c деревом отрезков">↵
```↵
#include <bits/stdc++.h>↵

using namespace std;↵
const int maxn = 2e5 + 12;↵

vector<int> g[maxn];↵
vector<int> ord;↵
int dp[maxn];↵
int n, m, k;↵

bool calc(int v, int p, int f){↵
    bool is = 0;↵
    if(v == f) is = 1;↵
    dp[v] = 1;↵
    for(int to:g[v]){↵
        if(to == p){↵
            continue;↵
        }↵
        bool fg = calc(to, v, f);↵
        is |= fg;↵
        if(fg == 0){↵
            dp[v] = max(dp[v], dp[to] + 1);↵
        }↵
    }↵
    if(is){↵
        ord.push_back(v);↵
    }↵
    return is;↵
}↵

struct segtree {↵
    int t[maxn * 4];↵
    void build (int v, int tl, int tr, vector <int>& a) {↵
        if (tl == tr) {↵
            t[v] = a[tl];↵
            return;↵
        }↵
        int tm = (tl + tr) >> 1;↵
        build (v * 2, tl, tm, a);↵
        build (v * 2 + 1, tm + 1, tr, a);↵
        t[v] = max(t[v * 2], t[v * 2 + 1]);↵
    }↵
    int get (int v, int tl, int tr, int l, int r) {↵
        if (tr < l || r < tl) return 0;↵
        if (l <= tl && tr <= r) return t[v];↵
        int tm = (tl + tr) >> 1;↵
        return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));↵
    }↵
} st_a, st_b;↵

int get(int v){↵
    ord.clear();↵
    calc(1, 0 , v);↵
    int m = ord.size();↵
    reverse(ord.begin(), ord.end());↵
    vector<int> a(m), b(m);↵
    for(int i=0;i<m;i++){↵
        a[i] = dp[ord[i]] + i;↵
        b[i] = dp[ord[m - i - 1]] + i;↵
    }↵
    st_a.build(1, 0, m-1, a);↵
    st_b.build(1, 0, m-1, b);↵
    for(int i=0;i < (m + 1) / 2;i++){↵
        if(a[i] > st_b.get(1, 0, m-1, i, m - i - 2)){↵
            return 1;↵
        }↵
        if(b[i] >= st_a.get(1, 0, m-1, i + 1, m - i - 2)){↵
            return 0;↵
        }↵
    }↵
}↵

void solve(){↵
    cin >> n;↵
    for(int i=1;i<=n;i++){↵
        g[i].clear();↵
    }↵
    for(int i=1;i<n;i++){↵
        int a, b;↵
        cin >> a >> b;↵
        g[a].push_back(b);↵
        g[b].push_back(a);↵
    }↵
    int u, v;↵
    cin >> u >> v;↵
    ord.clear();↵
    calc(v, 0, u);↵
    auto p = ord;↵
    for(int x:p){↵
        if(get(x) == 1){↵
            cout << "Alice\n";↵
        }↵
        else{↵
            cout << "Bob\n";↵
        }↵
    }↵
}↵

int main(){↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    int t = 1;↵
    cin >> t;↵
    while(t--){↵
        solve();↵
    }↵
}↵
```↵
</spoiler>↵

<spoiler summary="Решение за O(n)">↵
```↵
#include <bits/stdc++.h>↵

using namespace std;↵

int dfs(int v, int p, int to, const vector<vector<int>> &g, vector<int> &max_depth) {↵
    int ans = 0;↵
    bool has_to = false;↵
    for (int i : g[v]) {↵
        if (i == p) {↵
            continue;↵
        }↵
        int tmp = dfs(i, v, to, g, max_depth);↵
        if (tmp == -1) {↵
            has_to = true;↵
        } else {↵
            ans = max(ans, tmp + 1);↵
        }↵
    }↵
    if (has_to || v == to) {↵
        max_depth.emplace_back(ans);↵
        return -1;↵
    } else {↵
        return ans;↵
    }↵
}↵

int solve(const vector<vector<int>> &g, int to) {↵
    vector<int> max_depth;↵
    dfs(0, -1, to, g, max_depth);↵
    int n = max_depth.size();↵
    reverse(max_depth.begin(), max_depth.end());↵
    int first = 0, second = n - 1;↵
    while (true) {↵
        {↵
            int value1 = max_depth[first] + first;↵
            bool valid = true;↵
            for (int j = second; j > first; --j) {↵
                if (value1 <= max_depth[j] + (n - j - 1)) {↵
                    valid = false;↵
                    break;↵
                }↵
            }↵
            if (valid) {↵
                return 0;↵
            }↵
            ++first;↵
            if (first == second) {↵
                return 1;↵
            }↵
        }↵
        {↵
            int value2 = max_depth[second] + (n - second - 1);↵
            bool valid = true;↵
            for (int j = first; j < second; ++j) {↵
                if (value2 < max_depth[j] + j) {↵
                    valid = false;↵
                    break;↵
                }↵
            }↵
            if (valid) {↵
                return 1;↵
            }↵
            --second;↵
            if (first == second) {↵
                return 0;↵
            }↵
        }↵
    }↵
}↵

void solve() {↵
    int n;↵
    cin >> n;↵
    vector<vector<int>> g(n);↵
    for (int i = 0; i < n - 1; ++i) {↵
        int a, b;↵
        cin >> a >> b;↵
        g[a - 1].push_back(b - 1);↵
        g[b - 1].push_back(a - 1);↵
    }↵
    int s, f;↵
    cin >> s >> f;↵
    --s, --f;↵
    int ans = solve(g, s);↵
    if (ans == 0) {↵
        cout << "Alice\n";↵
    } else {↵
        cout << "Bob\n";↵
    }↵
}↵

int main() {↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(0);↵

    int t;↵
    cin >> t;↵
    while (t--)↵
        solve();↵
}↵
```↵
</spoiler>↵

[2013F2 &mdash; Игра на дереве (сложная версия)](https://mirror.codeforces.com/contest/2013/problem/F2)↵

Первый решивший: [user:rainboy,2024-09-21]↵

<spoiler summary="Разбор">↵
Прочтите разбор простой версии задачи.↵

Путь $(u, v)$ можно разбить на два вертикальных пути $(1, u)$ и $(1, v)$, далее мы будем решать для вершин на пути $(1, u)$, путь $(1, v)$ решается аналогично.↵

Для каждой вершины на пути $(1, u)$, введем два значения.↵

- $fa_i$ &mdash; Первая вершина на которой победит Алиса, если спустится в поддерево, когда Боб начинает с вершины $p_i$.↵
- $fb_i$ &mdash; Первая вершина на который Победит Боб если спустится в поддерево, когда Боб начинает с вершины $p_i$.↵

Утверждение, Алисе выгодно спускаться в поддерево вершины $v$, только на каком-то подотерзке вершин с которых начинает Боб. Аналогичное утверждение выполняется и для Боба.↵

Теперь нужно для каждой вершины Алисы, определить отрезок на котором нам будет выгодно спускаться. Левая граница отрезка для вершины $p_i$, будет равна $2 \cdot i$, так как Алиса всегда будет на левой половине пути. Не трудно заметить, что правую границу отрезка можно находиться с помощью бинарного поиска. ↵

Переопределим значение $b_i$, приравняем его к $d_{p_i} - i$. Чтобы проверить выгодно ли нам спускаться в поддереве для фиксированной середины $mid$, нам необходимо чтобы выполнялось следующее условие: $a_i > max(b_{i+1}, b_{i+2}, \ldots, b_{mid - i}) + mid$.↵

Обозначним за $(l_j, r_j)$, подотрезок на котором Алисе выгодно спуститься вниз, если Боб начнет с вершины $p_j$. Тогда значение $fa_i$ ,будет равно минимальной позиции $j$, на которой выполняется следующее условие: $l_j \leq i \leq r_j$, это можно находиться с использованием сета.  ↵

Значение $fb_i$, считается аналогично.↵

Алиса выигрывает на вершине $p_i$, если $fa_i \leq i - fb_i$, в противном случае побеждает Боб.↵

Для эффективного нахождения максимума на подотрезке, можно использовать разряженную таблицу. Также использование сетов и бинарных поисков дает нам временную сложность $O(nlogn)$.↵
</spoiler>↵

<spoiler summary="Решение">↵
```↵
#include <bits/stdc++.h>↵

using namespace std;↵
const int maxn = 2e5 + 12;↵

vector<int> g[maxn], del[maxn], add[maxn];↵
vector<int> ord;↵
int ans[maxn];↵
int dp[maxn];↵
int n, m, k;↵

bool calc(int v, int p, int f){↵
    bool is = 0;↵
    if(v == f) is = 1;↵
    dp[v] = 1;↵
    for(int to:g[v]){↵
        if(to == p){↵
            continue;↵
        }↵
        bool fg = calc(to, v, f);↵
        is |= fg;↵
        if(fg == 0){↵
            dp[v] = max(dp[v], dp[to] + 1);↵
        }↵
    }↵
    if(is){↵
        ord.push_back(v);↵
    }↵
    return is;↵
}↵

struct sparse {↵
    int mx[20][200200], lg[200200];↵
    int n;↵
    void build(vector<int> &a){↵
        n = a.size();↵
        for(int i=0;i<n;i++){↵
            mx[0][i] = a[i];↵
        }↵
        lg[0] = lg[1] = 0;↵
        for(int i=2;i<=n;i++){↵
            lg[i] = lg[i/2] + 1;↵
        }↵
        for(int k=1;k<20;k++){↵
            for(int i=0;i + (1 << k) - 1 < n;i++){↵
                mx[k][i] = max(mx[k-1][i], mx[k-1][i + (1 << (k - 1))]);↵
            }↵
        }↵
    }↵
    int get (int l, int r) {↵
        if(l > r) return -1e9;↵
        int k = lg[r-l+1];↵
        return max(mx[k][l], mx[k][r - (1 << k) + 1]);↵
    }↵
} st_a, st_b;↵

void solve(int v){↵
    ord.clear();↵
    calc(1, 0, v);↵
    reverse(ord.begin(), ord.end());↵
    m = ord.size();↵
    vector<int> a(m+1), b(m+1);↵
    vector<int> fa(m+1, 1e9), fb(m+1, -1e9);↵
    for(int i=0;i<m;i++){↵
        a[i] = dp[ord[i]] + i;↵
        b[i] = dp[ord[i]] - i;↵
        del[i].clear();↵
        add[i].clear();↵
    }↵
    st_a.build(a);↵
    st_b.build(b);↵
    multiset<int> s;↵
    for(int i=1;i<m;i++){↵
        int pos = i;↵
        for(int l=i+1, r=m-1;l<=r;){↵
            int mid = l + r >> 1;↵
            if(st_b.get(i+1 , mid) + mid < a[i] - i){↵
                pos = mid;↵
                l = mid + 1;↵
            }↵
            else r = mid - 1;↵
        }↵
        if(i < pos){↵
            add[min(m, 2 * i)].push_back(i);↵
            del[min(m, pos + i)].push_back(i);↵
        }↵
        for(int x:add[i]){↵
            s.insert(x);↵
        }↵
        if(s.size()) fa[i] = *s.begin();↵
        for(int x:del[i]){↵
            s.erase(s.find(x));↵
        }↵
    }↵
    s.clear();↵
    for(int i=0;i<=m;i++){↵
        add[i].clear();↵
        del[i].clear();↵
    }↵
    for(int i=1;i<m;i++){↵
        int pos = i;↵
        for(int l=1, r = i-1;l<=r;){↵
            int mid = l + r >> 1;↵
            if(st_a.get(mid, i-1) - mid + 1 <= b[i] + i){↵
                pos = mid;↵
                r = mid - 1;↵
            }↵
            else l = mid + 1;↵
        }↵
        pos--;↵
        if(pos >= 0){↵
            add[min(m, pos + i)].push_back(i);↵
            del[min(m, 2 * i - 1)].push_back(i);↵
        }↵
        for(int x:add[i]){↵
            s.insert(x);↵
        }↵
        if(s.size()) fb[i] = *s.rbegin();↵
        for(int x:del[i]){↵
            s.erase(s.find(x));↵
        }↵
    }↵
    for(int i=m-1;i>0;i--){↵
        b[i] = max(b[i+1] + 1, dp[ord[i]]);↵
        if(b[i] >= st_a.get(1, i-1)){↵
            fb[i] = i;↵
        }↵
        if(a[0] > max(st_b.get(1, i-1) + i, b[i])){↵
            fa[i] = 0;↵
        }↵
        ans[ord[i]] = 0;↵
        if(fa[i] <= i - fb[i]){↵
            ans[ord[i]] = 1;↵
        }↵
    }↵
}↵

void solve(){↵
    cin >> n;↵
    for(int i=1;i<=n;i++){↵
        g[i].clear();↵
    }↵
    for(int i=1;i<n;i++){↵
        int a, b;↵
        cin >> a >> b;↵
        g[a].push_back(b);↵
        g[b].push_back(a);↵
    }↵
    int u, v;↵
    cin >> u >> v;↵
    solve(u), solve(v);↵
    ord.clear();↵
    calc(v, 0, u);↵
    auto p = ord;↵
    for(int x:p){↵
        if(ans[x] == 1){↵
            cout << "Alice\n";↵
        }↵
        else{↵
            cout << "Bob\n";↵
        }↵
    }↵
}↵

int main(){↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    int t = 1;↵
    cin >> t;↵
    while(t--){↵
        solve();↵
    }↵
}↵
```↵
</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru26 Русский Wansur 2024-09-22 19:27:59 6 Мелкая правка: ', пока он меньше, чем $' -> ', пока он больше, чем $'
en10 Английский Wansur 2024-09-22 19:27:29 9 Tiny change: 'ile it is less than $ \f' -> 'ile it is greater than $ \f'
en9 Английский Wansur 2024-09-22 08:01:16 2 Tiny change: '3/problem/D)\n\nFirst' -> '3/problem/E)\n\nFirst'
ru25 Русский Wansur 2024-09-22 08:00:53 2 Мелкая правка: '3/problem/D)\n\nПервы' -> '3/problem/E)\n\nПервы'
en8 Английский Wansur 2024-09-22 00:44:44 20
en7 Английский Wansur 2024-09-22 00:44:18 15 (published)
ru24 Русский Wansur 2024-09-22 00:41:47 0 (опубликовано)
en6 Английский Wansur 2024-09-22 00:40:30 2845
ru23 Русский Wansur 2024-09-22 00:31:45 20 Мелкая правка: 'ую вершину в своих поддеревьях.\n\nПусть' -> 'ую вершину.\n\nПусть'
en5 Английский Wansur 2024-09-22 00:31:19 5406
en4 Английский Wansur 2024-09-22 00:26:45 6 Tiny change: 't) \) and \( \left( \f' -> 't) \) and $ \left( \f'
en3 Английский Wansur 2024-09-22 00:24:38 3429
en2 Английский Wansur 2024-09-22 00:13:29 941 Tiny change: ' Если $x \leq y$. В э' -> ' Если $x \geq y$. В э'
ru22 Русский Wansur 2024-09-22 00:09:55 2 Мелкая правка: ' Если $x \leq y$. В э' -> ' Если $x \req y$. В э'
ru21 Русский Wansur 2024-09-22 00:09:17 6 Мелкая правка: '- Если $x >= y$. В это' -> '- Если $x \leq y$. В это'
en1 Английский Wansur 2024-09-22 00:09:01 21327 Initial revision for English translation (saved to drafts)
ru20 Русский Wansur 2024-09-21 23:58:12 333
ru19 Русский Wansur 2024-09-21 23:51:09 1880 Мелкая правка: 'читываем $\sum$ и $cn' -> 'читываем $sum$ и $cn'
ru18 Русский Wansur 2024-09-21 22:51:42 31 Мелкая правка: 'ого поиска, потому-что функция монотонная. \n\nПере' -> 'ого поиска. \n\nПере'
ru17 Русский Wansur 2024-09-21 22:49:26 5877 Мелкая правка: 'о функция будет монотонно. \n\nПере' -> 'о функция монотонная. \n\nПере'
ru16 Русский Wansur 2024-09-21 21:55:55 583 Мелкая правка: 'ов (где $c ---$ это колич' -> 'ов (где $c$ --- это колич'
ru15 Русский Wansur 2024-09-21 21:38:01 96 Мелкая правка: 'е $p_1 = 1 и $p_m = ' -> 'е $p_1 = 1$ и $p_m = '
ru14 Русский Wansur 2024-09-21 21:33:03 1438
ru13 Русский Wansur 2024-09-21 21:22:45 3367 Мелкая правка: 'n}\n```\n<\spoiler>\n' -> 'n}\n```\n</spoiler>\n'
ru12 Русский Wansur 2024-09-21 20:58:06 3016
ru11 Русский Wansur 2024-09-21 14:07:09 1544 Мелкая правка: 'менты.\n\n<spoiler' -> 'менты.\n\nВременная сложность $O(n \cdot 10)$.\n<spoiler'
ru10 Русский Wansur 2024-09-21 13:29:36 801 Мелкая правка: '0$ и $t + 0$. Если од' -> '0$ и $t + 1$. Если од'
ru9 Русский Wansur 2024-09-21 12:47:43 519
ru8 Русский Wansur 2024-09-21 12:38:46 578
ru7 Русский Wansur 2024-09-21 12:32:49 248
ru6 Русский Wansur 2024-09-21 10:55:13 48 Мелкая правка: 'oblem/D)\n' -> 'oblem/D)\n\n\n<spoiler summary="Разбор">\n\n</spoiler>\n\n'
ru5 Русский Wansur 2024-09-20 22:41:14 1709
ru4 Русский Wansur 2024-09-20 20:14:43 247 Мелкая правка: 'е">\n```\n\n#include' -> 'е">\n```\n#include'
ru3 Русский Wansur 2024-09-20 20:07:09 73 Мелкая правка: 'вет это $\ceil*{\frac{n}{' -> 'вет это $\rceil{\frac{n}{'
ru2 Русский Wansur 2024-09-20 20:00:12 6 Мелкая правка: '{\frac{n}{\min(x, y)}' -> '{\frac{n}{min(x, y)}'
ru1 Русский Wansur 2024-09-20 19:29:47 552 Первая редакция (сохранено в черновиках)