[2013A — Блендер Жана](https://codeforces.me/contest/2013/problem/A)↵
↵
Первый решивший: [user:rob00,2024-09-21]↵
↵
<spoiler summary="Разбор">↵
Давайте рассмотрим $2$ случая.↵
↵
- Если $x \geq y$. В этом случае, каждую секунду блендер будет смешивать $min(y, c)$ фруктов (где $c$ — это количество не смешанных фруктов). 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 — Бой на выживание](https://codeforces.me/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 — Взлом Пароля](https://codeforces.me/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 — Минимизировать разность](https://codeforces.me/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 — Префиксные НОД](https://codeforces.me/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 — Игра на дереве (простая версия)](https://codeforces.me/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 — Игра на дереве (сложная версия)](https://codeforces.me/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$ — Первая вершина на которой победит Алиса, если спустится в поддерево, когда Боб начинает с вершины $p_i$.↵
- $fb_i$ — Первая вершина на который Победит Боб если спустится в поддерево, когда Боб начинает с вершины $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>↵
↵
↵
Первый решивший: [user:rob00,2024-09-21]↵
↵
<spoiler summary="Разбор">↵
Давайте рассмотрим $2$ случая.↵
↵
- Если $x \geq y$. В этом случае, каждую секунду блендер будет смешивать $min(y, c)$ фруктов (где $c$ — это количество не смешанных фруктов). 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 — Бой на выживание](https://codeforces.me/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 — Взлом Пароля](https://codeforces.me/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 — Минимизировать разность](https://codeforces.me/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$. Мы будем удалять последний элемент из стека, пока он
↵
Временная сложность алгоритма — $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 — Префиксные НОД](https://codeforces.me/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 — Игра на дереве (простая версия)](https://codeforces.me/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 — Игра на дереве (сложная версия)](https://codeforces.me/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$ — Первая вершина на которой победит Алиса, если спустится в поддерево, когда Боб начинает с вершины $p_i$.↵
- $fb_i$ — Первая вершина на который Победит Боб если спустится в поддерево, когда Боб начинает с вершины $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>↵
↵
