Большое спасибо всем за участие! Отдельное спасибо [user:China001,2026-01-25] и [user:daki-sa,2026-01-25] за альтернативное решение задачи H.↵
↵
[problem:2193A]↵
↵
- Идея: [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказка">↵
Каждая операция увеличивает сумму ровно на $x$ вне зависимости от индекса, на который была применена операция.↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Обозначим $A$ как изначальную сумму массива $a$. Каждая операция прибавляет $x$ к $A$. Нам нужно проверить, может ли $A$ стать равным $S$. Во первых, $S$ не должен быть меньше, чем $A$. Во вторых, их разница должна делиться на $x$, то есть $x$ должен делить ($S-A$).↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main()↵
{↵
int t;↵
cin >> t;↵
↵
while( t -- )↵
{↵
int n, s, x;↵
cin >> n >> s >> x;↵
int a[n + 5], sum = 0;↵
↵
for( int i = 1; i <= n; i ++ ) cin >> a[i], sum += a[i];↵
↵
if( sum > s || (s - sum) % x != 0 ) cout << "NO\\n";↵
else cout << "YES\\n";↵
}↵
}↵
↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:A,option1] Классная задача↵
- [likes:A,option2] Нормальная задача↵
- [likes:A,option3] Плохая задача↵
- [likes:A,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193B]↵
↵
- Идея: [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказки">↵
↵
<spoiler summary="Подсказка 1">↵
В оптимальной перестановке, первый элемент всегда равен $n$.↵
</spoiler>↵
↵
↵
<spoiler summary="Подсказка 2">↵
Нужно найти минимальный индекс $i$, который можно увеличить с помощью операции. Этот $i$ и будет левой границей в операции.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Если $p_1 = n$, то менять его нет смысла. Если $p_1 = n$ и $p_2 = n-1$, то и второй элемент менять не нужно и так далее. Таким образом, нам нужно найти первый индекс $i$, для которого $p_i\neq n-i+1$ и увеличить его. Наша цель — приравнять $p_i$ к $n-i+1$ (тогда перестановка будет максимальна лексикографически). Найдем индекс $j$ такой, что $p_j$ равен $n-i+1$ и сделаем операцию $[i, j]$.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main()↵
{↵
int t;↵
cin >> t;↵
↵
while( t -- )↵
{↵
int n;↵
cin >> n;↵
↵
int p[n + 5], ind = 1;↵
↵
for( int i = 1; i <= n; i ++ )↵
{↵
cin >> p[i];↵
}↵
while( ind <= n && p[ind] == n - ind + 1 ) ind ++;↵
int id = -1;↵
↵
for( int i = ind; i <= n; i ++ )↵
{↵
if( p[i] == n - ind + 1 ) id = i;↵
}↵
for( int i = 1; i < ind; i ++ ) cout << p[i] << ' ';↵
↵
if( id != -1 )↵
{↵
for( int i = id; i >= ind; i -- ) cout << p[i] << ' ';↵
for( int i = id + 1; i <= n; i ++ ) cout << p[i] << ' ';↵
}↵
cout << '\\n';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:B,option1] Классная задача↵
- [likes:B,option2] Нормальная задача↵
- [likes:B,option3] Плохая задача↵
- [likes:B,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193C]↵
↵
- Идея: [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказка">↵
Для начала, попытаемся максимизировать все элементы $a$, а после ответим на запросы.↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Для начала, попытаемся максимизировать все элементы $a$, а после ответим на запросы. Переберем $i$ от $n$ до $1$ и приравняем $a_i$ к максимуму среди $a_i$, $b_i$ и $a_{i+1}$. Таким образом, каждый $a_i$ достигает максимального значения. Теперь мы можем написать префиксные суммы на массиве $a$, чтобы отвечать за $O(1)$ на каждый запрос.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
#define int long long↵
↵
using namespace std;↵
↵
signed main()↵
{↵
int t; cin >> t;↵
↵
while( t -- )↵
{↵
int n, q; cin >> n >> q;↵
int a[n + 5], b[n + 5], pref[n + 5], ans = 0;↵
↵
for( int i = 1; i <= n; i ++ ) cin >> a[i];↵
for( int i = 1; i <= n; i ++ ) cin >> b[i];↵
↵
a[n + 1] = 0;↵
↵
for( int i = n; i > 0; i -- ) a[i] = max({a[i], a[i + 1], b[i]});↵
↵
pref[0] = 0;↵
for( int i = 1; i <= n; i ++ ) pref[i] = pref[i - 1] + a[i];↵
↵
for( int i = 1; i <= q; i ++ ){↵
int L, R; cin >> L >> R;↵
cout << pref[R] - pref[L - 1] << " ";↵
}↵
cout << "\n";↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:C,option1] Классная задача↵
- [likes:C,option2] Нормальная задача↵
- [likes:C,option3] Плохая задача↵
- [likes:C,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193D]↵
↵
- Идея: [user:YF_YUSUF,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказки">↵
↵
<spoiler summary="Подсказка 1">↵
Чем больше сложность, тем меньше мечей можно использовать. Чем меньше мечей можно использовать, тем меньше уровней можно пройти.↵
</spoiler>↵
↵
↵
<spoiler summary="Подсказка 2">↵
Если оптимальная сложность равна $x$, то хотя бы один элемент в массиве $a$ равен $x$. В противном случае, мы бы могли увеличить $x$, не потеряв мечи.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Отсортируем все мечи по силе в порядке убывания. Тогда если сложность равна $a_i$, то количество мечей, которые можно использовать, равно $i$. По мере уменьшения сложности растет количество мечей, а значит и количество уровней, которые можно пройти. Можно поддерживать указатель на количество уровней и брать максимальный счет среди всех сложностей. Такое решение с указателем работает за $O(n)$ операций.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const int N = 2e5 + 12;↵
↵
int t, n, a[N], b[N];↵
↵
int main()↵
{↵
cin >> t;↵
↵
while( t -- )↵
{↵
cin >> n;↵
↵
for( int i = 1; i <= n; i ++ ) cin >> a[i];↵
for( int i = 1; i <= n; i ++ ) cin >> b[i];↵
↵
int h = 0, sum = 0; ll ans = 0;↵
sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);↵
↵
for( int i = 1; i <= n; i ++ )↵
{↵
while( h < n && sum + b[h + 1] <= i ) h ++, sum += b[h];↵
ans = max(ans, a[i] * 1ll * h);↵
}↵
cout << ans << '\n';↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:D,option1] Классная задача↵
- [likes:D,option2] Нормальная задача↵
- [likes:D,option3] Плохая задача↵
- [likes:D,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193E]↵
↵
- Идея: [user:Wansur,2026-01-25]↵
- Решение + разбор: [user:Wansur,2026-01-25]↵
↵
<spoiler summary="Подсказка">↵
Попробуйте дп подход к задаче.↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Будем писать динамику. $dp[x]$ это ответ для числа $x$. Изначально $dp[a_i] = 1$ для всех $i$ от $1$ до $n$, все остальные элементы $dp$ будут равны $10^9$. Переберем $x$ от $1$ до $n$ и рассмотрим переход:↵
↵
- Переберем все делители $y$ числа $x$.↵
- Обновим $dp[x]$ на $min(dp[x], dp[y] + dp[\frac{x}{y}])$.↵
↵
Заменим все $dp[x]$ равные $10^9$ на $-1$ и выведем все значения $dp$. В решении мы перебрали все числа от $1$ до $n$ и их делителей, суммарно это $O(n \log n)$ операций.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
const int maxn = 1'000'012;↵
↵
int a[maxn], dp[maxn];↵
int n, q;↵
↵
void solve() {↵
cin >> n;↵
↵
for(int i = 1; i <= n; i++) {↵
dp[i] = 1e9;↵
}↵
for(int i = 1; i <= n;i++) {↵
cin >> a[i];↵
dp[a[i]] = 1;↵
}↵
↵
for(int i = 1; i <= n; i++) {↵
for(int j = i; j <= n; j += i) {↵
dp[j] = min(dp[j], dp[i] + dp[j / i]);↵
}↵
}↵
↵
for(int i = 1; i <= n; i++) {↵
if(dp[i] == 1e9) {↵
dp[i] = -1;↵
}↵
cout << dp[i] << " \n"[i == n];↵
}↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t = 1;↵
cin >> t;↵
while(t--) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:E,option1] Классная задача↵
- [likes:E,option2] Нормальная задача↵
- [likes:E,option3] Плохая задача↵
- [likes:E,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193F]↵
↵
- Идея: [user:YF_YUSUF,2026-01-25], [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказки">↵
↵
<spoiler summary="Подсказка 1">↵
Для двух точек $(x_i, y_i)$ и $(x_j, y_j)$, если $x_i\lt x_j$, то доставить пиццу в точку $i$ нужно раньше, чем в точку $j$ (потому что из $(x, y)$ мы не можем пойти в $(x-1, y)$).↵
</spoiler>↵
↵
↵
<spoiler summary="Подсказка 2">↵
Попробуйте дп подход к задаче.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Разобьем точки доставки на группы с одинаковым $x_i$. Пронумеруем группы от $0$ до $m+1$ в порядке возрастания $x_i$, где $m$ это количество различных $x_i$. Группа $0$ это точка старта и группа $m+1$ это точка финиша.↵
↵
Поскольку мы не можем делать ходы влево, нужно доставить пиццу во все точки группы $i$, прежде чем перейти к группе $i+1$. Обозначим $high_i$ как точку с максимальным значением $y$ и $low_i$ как точку с минимальным значением $y$ в группе $i$. Поскольку все точки в группе находятся между ними, для группы, точкой куда доставят пиццу в последнюю очередь, окажется одна из них. Это означает, что переходить из группы $i$ в группу $i+1$ мы будем либо через $high_i$, либо через $low_i$.↵
↵
Теперь мы можем написать динамику на задачу. $dp[i][0]$ это минимальное количество времени для того, чтобы доставить пиццу во все группы от $0$ до $i$, последней доставив в точку $high_i$, и $dp[i][1]$ с точкой $low_i$ соответственно. Изначально, $dp[0][0] = 0$ и $dp[0][1] = 0$. Для всех других $i\gt 0$, переходы будут следующие:↵
↵
- $dp[i][0] = min(dp[i - 1][0] + dist(high_{i-1}, low_i), dp[i - 1][1] + dist(low_{i-1}, low_i)) + dist(low_i, high_i);$↵
- $dp[i][1] = min(dp[i - 1][0] + dist(high_{i-1}, high_i), dp[i - 1][1] + dist(low_{i-1}, high_i)) + dist(high_i, low_i);$↵
↵
Тут $dist(a, b)$ означает манхэттенское расстояние между точками $a$, $b$. Таким образом, на сортировку всех точек по группам уходит $O(n \log n)$ операций, а на подсчет динамики $O(n)$ операций.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
#define F first↵
#define S second↵
#define int long long↵
↵
using namespace std;↵
↵
int t, n, ax, ay, bx, by;↵
↵
signed main()↵
{↵
cin >> t;↵
↵
while( t -- )↵
{↵
cin >> n >> ax >> ay >> bx >> by;↵
vector <int> x(n + 5), y(n + 5), dp[2];↵
↵
dp[0] = dp[1] = vector <int> (n + 5, 0);↵
map <int, int> mx, mn;↵
↵
mn[ax] = mx[ax] = ay;↵
mn[bx] = mx[bx] = by;↵
↵
for( int i = 0; i < n; i ++ ) cin >> x[i];↵
for( int i = 0; i < n; i ++ ) cin >> y[i];↵
↵
for( int i = 0; i < n; i ++ )↵
{↵
mx[x[i]] = max(mx[x[i]], y[i]);↵
↵
if(!mn.count(x[i])) mn[x[i]] = y[i];↵
else mn[x[i]] = min(mn[x[i]], y[i]);↵
}↵
int lst = ax, cnt = 0;↵
↵
for( auto i : mx )↵
{↵
if( i.F == ax )↵
{↵
dp[0][0] = dp[1][0] = 0;↵
continue;↵
}↵
int need = (i.F - lst) + (mx[i.F] - mn[i.F]);↵
cnt ++;↵
↵
dp[0][cnt] = min(dp[0][cnt - 1] + abs(mx[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mx[i.F] - mx[lst])) + need;↵
dp[1][cnt] = min(dp[0][cnt - 1] + abs(mn[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mn[i.F] - mx[lst])) + need;↵
↵
lst = i.F;↵
}↵
cout << dp[0][cnt] << '\n';↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:F,option1] Классная задача↵
- [likes:F,option2] Нормальная задача↵
- [likes:F,option3] Плохая задача↵
- [likes:F,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193G]↵
↵
- Идея: [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:Wansur,2026-01-25], [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказка">↵
Попробуйте разделить вершины по парам и запрашивать у интерактора эти пары.↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Для начала, выпишем номера всех вершин дерева в последовательность $p$ в порядке обхода дфс. Разделим элементы последовательности $p$ по парам $(p_1, p_2)$, $(p_3, p_4)$ и так далее. Если $n$ нечетный, то временно забудем о последнем элементе.↵
↵
Переберем $i$ от 1 до $\frac{n}{2}$ и будем делать интерактору следующий запрос: $?$ $p_{2i-1}$ $p_{2i}$.↵
↵
- Если это две смежные вершины, то тогда, когда интерактор ответит $1$, мы будем однозначно знать, что хотя бы одна из вершин лежит на пути. В этом случае, мы можем за дополнительный запрос, узнать какая из двух вершин лежит на пути.↵
- Иначе, посмотрим на простой путь между двумя вершинами. Все пары до этой пары мы опросили, значит на их пути только они не были опрошены. Тогда, мы вернулись в ту же ситуацию, когда одна из вершин однозначно лежит на пути (если интерактор ответит положительно).↵
- Если мы нашли подходящую вершину, прекратим процесс.↵
↵
Когда $n$ нечетен, остается одна неопрошенная вершина. Если мы не нашли вершину из скрытого пути ни в одной паре, то однозначно можно сказать, что оставшаяся вершина и есть та, которая лежит на скрытом пути. В итоге мы получаем решение, которое работает ровно за $\lfloor\frac{n}{2}\rfloor$ + 1 запросов.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
#define sz(x) (int)(x.size())↵
#define pb push_back↵
↵
using namespace std; ↵
const int N = 2e5 + 12;↵
↵
int n, x, y, a, b;↵
vector <int> L, g[N];↵
↵
void dfs( int v, int p = 0 )↵
{↵
L.pb(v);↵
↵
for( auto to : g[v] )↵
{↵
if( to != p ) dfs(to, v);↵
}↵
}↵
int ask( int a, int b )↵
{↵
cout << "? " << a << ' ' << b << endl;↵
int res; cin >> res; return res;↵
}↵
void solve()↵
{↵
cin >> n;↵
↵
L.clear();↵
for( int i = 1; i <= n; i ++ ) g[i].clear();↵
↵
for( int i = 1; i < n; i ++ )↵
{↵
cin >> a >> b;↵
g[a].pb(b), g[b].pb(a);↵
}↵
dfs(1, 0);↵
↵
for( int i = 0; i < sz(L) - 1; i += 2 )↵
{↵
a = L[i], b = L[i + 1];↵
↵
if( ask(a, b) == 1 )↵
{↵
if( ask(a, a) == 1 ) cout << "! " << a << endl;↵
else cout << "! " << b << endl;↵
return;↵
}↵
}↵
cout << "! " << L.back() << endl;↵
}↵
int main()↵
{↵
int t; cin >> t;↵
while( t -- ) solve();↵
}↵
```↵
↵
## </spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:G,option1] Классная задача↵
- [likes:G,option2] Нормальная задача↵
- [likes:G,option3] Плохая задача↵
- [likes:G,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193H]↵
↵
- Идея: [user:Mendeke,2026-01-25]↵
- Решение + разбор: [user:Wansur,2026-01-25], [user:China001,2026-01-25], [user:daki-sa,2026-01-25] и [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Основное решение">↵
Для начала возьмем все элементы по модулю $2$. Теперь все элементы равны единицам и нулям. Можно заметить, что если удалить все $a_i$, которые равны нулю, то $S_v$ для других не изменится. Удалим все $a_i$ равные нулю, у которых изначальный $S_v$ нечетен, если $S_v$ равен нулю, то ответа нет. Тех $v$, у которых $S_v$ четен, мы удаляем по мере удаления единиц.↵
↵
Теперь нужно разобраться с единицами. Всех $v$, у которых $a_v$ равен нулю, удалим из графа, оставив лес (граф из нескольких несвязных деревьев) из единиц. Решим задачу для каждого нового дерева из единиц. Для какого-то дерева из единиц размера $n$, ответа нет, когда $n$ четен. Когда $n$ четен, количество ребер нечетно, но каждое удаление удаляет одну вершину и четное количество ребер. Отнимая от изначального нечетного количество ребер четные числа, мы никогда не достигнем нуля ребер (то есть пустого графа). Теперь сделаем утверждение — когда $n$ нечетен, ответ есть всегда.↵
↵
Скажем, что для пары смежных вершин $(v, u)$, $v$ дает вклад в $u$ тогда, когда при удаление $u$, компонента вершины $v$ становится четного размера. Обозначим $f(v)$ как количество вершин, дающих вклад в $v$. Можно понять, что удалять нужно ту вершину, у которой $f(v)$ равен нулю. Компоненты всех соседей у такой вершины нечетного размера, а для получения нечетного $n$, нам нужно чтобы у нее было четное количество соседей (значит мы однозначно сможем удалить ее из графа). Теперь утверждается, что такая вершина всегда есть.↵
↵
<spoiler summary="Доказательство">↵
Рассмотрим какое-то ребро $(v, u)$ в дереве, поскольку $n$ нечетен, вклад дает либо $v$ в $u$, либо $u$ в $v$. Получается, сумма по всем $f(v)$ равна $n-1$, а значит по принципу Дирихле существует вершина, у которой $f(v)$ равен нулю, что и требовалось доказать.↵
</spoiler>↵
↵
Можно заметить, что после удаления вершины $v$, значения $f$ меняются только для соседей $v$. Для всех соседей $u$ вершины $v$ значение $f(u)$ уменьшается на $1$, ведь вклад давался из $v$ в $u$. Один раз посчитаем все значения $f$, и с помощью BFS будем удалять вершины, у которых значения $f$ равно нулю. Также не будем забывать, что некоторые нулю нужно удалить по мере удаления единиц. Это решение работает за O(n) операций.↵
</spoiler>↵
↵
↵
<spoiler summary="Второе решение">↵
Скажем, что корень дерева это вершина $1$. Будем писать динамику для задачи. Обозначим ее следующим образом:↵
↵
- $dp_v = 0$, если вершину $v$ удалить невозможно↵
- $dp_v = 1$, если для удаления вершины $v$, родитель вершины $v$ обязательно должен удаляться раньше вершины $v$.↵
- $dp_v = 2$, если для удаления вершины $v$, вершина $v$ обязательно должна удаляться раньше своего родителя.↵
- $dp_v = 3$, если для удаления вершины $v$ неважно, удалим мы родителя вершины или саму вершину первой.↵
↵
Если хотя бы для одного $v$, $dp_v$ равен нулю, то ответа не будет. Обозначим $p_v$ как родителя вершины $v$ и $s_v$ как сумму всех значений $a_u$, где $u$ это ребенок вершины $v$ и $dp_u$ равен $1$ или $3$. Для того, чтобы $dp_v$ был равен $1$, должно выполняться как минимум одно из двух условий:↵
↵
- $s_v$ по четности не равен $a_v$.↵
- $s_v$ по четности равен $a_v$, но у вершины есть ребенок $u$, для которого $dp_u = 3$ и $a_u = 1$. То есть, мы можем удалить $u$ раньше, чем $v$, тем самым изменив четность $s_v$.↵
↵
Прибавим $a_{p_v}$ к $s_v$ и проверим условия еще раз для $dp_v = 2$. Если в обоих случаях условия выполняются, то $dp_v = 3$, а если никакое не выполняется, то $dp_v = 0$. Осталось просто восстановить ответ по динамике, подробности можете посмотреть в реализации. Асимптотика решения — $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация основного решения">↵
↵
```↵
#include <bits/stdc++.h>↵
#define ent '\n'↵
#define int long long↵
↵
using namespace std;↵
const int maxn = 200'012;↵
const int mod = 1e9 + 7;↵
↵
int cnt[maxn], a[maxn], del[maxn];↵
int sz[maxn], bad[maxn], used[maxn];↵
vector<int> g[maxn], e[maxn], g2[maxn];↵
int n, m;↵
↵
void dfs(int v, int p) {↵
sz[v] = 1;↵
used[v] = true;↵
for(int to : g[v]) {↵
if(to == p) {↵
continue;↵
}↵
↵
dfs(to, v);↵
↵
if(sz[to] % 2 == 0) {↵
e[to].push_back(v);↵
bad[v]++;↵
}↵
else {↵
e[v].push_back(to);↵
bad[to]++;↵
}↵
↵
sz[v] += sz[to];↵
}↵
}↵
↵
void solve() {↵
cin >> n;↵
for(int i = 1; i <= n; i++) {↵
cin >> a[i];↵
a[i] %= 2;↵
del[i] = cnt[i] = sz[i] = 0;↵
bad[i] = used[i] = 0;↵
g[i].clear();↵
g2[i].clear();↵
e[i].clear();↵
}↵
↵
for(int i = 1; i < n; i++) {↵
int u, v;↵
cin >> u >> v;↵
↵
cnt[u] += a[v], cnt[v] += a[u];↵
↵
if(a[u] && a[v]) {↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
if( a[u] && !a[v] ) g2[u].push_back(v);↵
if( a[v] && !a[u] ) g2[v].push_back(u);↵
}↵
queue <int> q;↵
↵
for(int i = 1; i <= n; i++) {↵
if(!cnt[i] && !a[i]) {↵
cout << "NO\n";↵
return;↵
}↵
}↵
for(int i = 1; i <= n; i++) {↵
if(a[i] && !used[i]) {↵
dfs(i, 0);↵
if(sz[i] % 2 == 0) {↵
cout << "NO\n";↵
return;↵
}↵
}↵
}↵
for(int i = 1; i <= n; i++) {↵
if(a[i] && !bad[i]) {↵
q.push(i);↵
}↵
}↵
cout << "YES\n";↵
int zero[n + 5];↵
↵
for( int i = 1; i <= n; i ++ ){↵
zero[i] = 0;↵
↵
if( !a[i] && cnt[i] % 2 ) cout << i << ' ';↵
else if( !a[i] ) zero[i] = 1;↵
}↵
while(!q.empty()) {↵
int v = q.front(); q.pop();↵
cout << v << ' ';↵
for(int to : g2[v]){↵
if(zero[to]) cout << to << ' ', zero[to] = 0;↵
}↵
for(int to : e[v]) {↵
bad[to]--;↵
if(bad[to] == 0) q.push(to);↵
}↵
}↵
cout << ent;↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t = 1;↵
cin >> t;↵
while(t--) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация второго решения">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 2e5 + 12;↵
const int inf = 1e9 + 1;↵
↵
int n, x, y, a[N], dp[N], cnt[N], par[N];↵
vector <int> g[N], g2[N]; bool flag, used[N];↵
pair <int, int> must[N][3]; vector <int> ord;↵
↵
void dfs( int v, int p = 0 )↵
{↵
int s = 0, ok = 0, id = 0;↵
par[v] = p; ord.push_back(v);↵
↵
for( auto to : g[v] )↵
{↵
if( to == p ) continue;↵
↵
dfs(to, v);↵
if(!flag) return;↵
↵
if( dp[to] == 1 || dp[to] == 3 )↵
{↵
s ^= a[to];↵
↵
if( dp[to] == 3 && a[to] == 1 )↵
{↵
if( !ok )↵
{↵
ok = 1;↵
id = to;↵
}↵
}↵
if( dp[to] == 3 && id != to ) dp[to] = 1;↵
}↵
}↵
if( !ok && s == a[v] && (s + a[p]) % 2 == a[v] )↵
{↵
flag = 0;↵
return;↵
}↵
if( s != a[v] || ok )↵
{↵
if( s == a[v] ) must[v][1] = {id, 2};↵
else if(ok) must[v][1] = {id, 1};↵
↵
dp[v] = 1;↵
}↵
s = (s + a[p]) % 2;↵
↵
if( s != a[v] || ok )↵
{↵
if( s == a[v] ) must[v][2] = {id, 2};↵
else if(ok) must[v][2] = {id, 1};↵
↵
dp[v] += 2;↵
}↵
}↵
void dfs2( int v, int tp )↵
{↵
dp[v] = tp, used[v] = 1;↵
pair <int, int> p = must[v][tp];↵
if( p.first != 0 ) dfs2(p.first, p.second);↵
}↵
void solve()↵
{↵
cin >> n;↵
flag = 1;↵
↵
// dp[v] = 1, if p[v] before v↵
// dp[v] = 2, if v before p[v]↵
↵
for( int i = 1; i <= n; i ++ )↵
{↵
cin >> a[i];↵
a[i] %= 2;↵
↵
must[i][1] = must[i][2] = {0, 0};↵
dp[i] = cnt[i] = used[i] = 0;↵
g[i].clear(), g2[i].clear();↵
}↵
for( int i = 1; i < n; i ++ )↵
{↵
cin >> x >> y;↵
↵
g[x].push_back(y);↵
g[y].push_back(x);↵
}↵
ord.clear();↵
dfs(1);↵
↵
if( !flag )↵
{↵
cout << "No\n";↵
return;↵
}↵
cout << "Yes\n";↵
↵
for( auto i : ord )↵
{↵
if( !used[i] )↵
{↵
if( dp[i] == 3 ) dfs2(i, 1);↵
else dfs2(i, dp[i]);↵
}↵
}↵
for( int v = 2; v <= n; v ++ )↵
{↵
if( dp[v] == 1 ) cnt[v] ++, g2[par[v]].push_back(v);↵
else cnt[par[v]] ++, g2[v].push_back(par[v]);↵
}↵
queue <int> q;↵
↵
for( int i = 1; i <= n; i ++ )↵
{↵
if( cnt[i] == 0 ) q.push(i);↵
}↵
while( !q.empty() )↵
{↵
int v = q.front();↵
q.pop(); cout << v << ' ';↵
↵
for( auto to : g2[v] )↵
{↵
cnt[to] --;↵
if( !cnt[to] ) q.push(to);↵
}↵
}↵
cout << '\n';↵
}↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
↵
int t; cin >> t;↵
while(t --) solve();↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:H,option1] Классная задача↵
- [likes:H,option2] Нормальная задача↵
- [likes:H,option3] Плохая задача↵
- [likes:H,option4] Не решил↵
↵
</spoiler>↵
↵
↵
[problem:2193A]↵
↵
- Идея: [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказка">↵
Каждая операция увеличивает сумму ровно на $x$ вне зависимости от индекса, на который была применена операция.↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Обозначим $A$ как изначальную сумму массива $a$. Каждая операция прибавляет $x$ к $A$. Нам нужно проверить, может ли $A$ стать равным $S$. Во первых, $S$ не должен быть меньше, чем $A$. Во вторых, их разница должна делиться на $x$, то есть $x$ должен делить ($S-A$).↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main()↵
{↵
int t;↵
cin >> t;↵
↵
while( t -- )↵
{↵
int n, s, x;↵
cin >> n >> s >> x;↵
int a[n + 5], sum = 0;↵
↵
for( int i = 1; i <= n; i ++ ) cin >> a[i], sum += a[i];↵
↵
if( sum > s || (s - sum) % x != 0 ) cout << "NO\\n";↵
else cout << "YES\\n";↵
}↵
}↵
↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:A,option1] Классная задача↵
- [likes:A,option2] Нормальная задача↵
- [likes:A,option3] Плохая задача↵
- [likes:A,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193B]↵
↵
- Идея: [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказки">↵
↵
<spoiler summary="Подсказка 1">↵
В оптимальной перестановке, первый элемент всегда равен $n$.↵
</spoiler>↵
↵
↵
<spoiler summary="Подсказка 2">↵
Нужно найти минимальный индекс $i$, который можно увеличить с помощью операции. Этот $i$ и будет левой границей в операции.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Если $p_1 = n$, то менять его нет смысла. Если $p_1 = n$ и $p_2 = n-1$, то и второй элемент менять не нужно и так далее. Таким образом, нам нужно найти первый индекс $i$, для которого $p_i\neq n-i+1$ и увеличить его. Наша цель — приравнять $p_i$ к $n-i+1$ (тогда перестановка будет максимальна лексикографически). Найдем индекс $j$ такой, что $p_j$ равен $n-i+1$ и сделаем операцию $[i, j]$.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
int main()↵
{↵
int t;↵
cin >> t;↵
↵
while( t -- )↵
{↵
int n;↵
cin >> n;↵
↵
int p[n + 5], ind = 1;↵
↵
for( int i = 1; i <= n; i ++ )↵
{↵
cin >> p[i];↵
}↵
while( ind <= n && p[ind] == n - ind + 1 ) ind ++;↵
int id = -1;↵
↵
for( int i = ind; i <= n; i ++ )↵
{↵
if( p[i] == n - ind + 1 ) id = i;↵
}↵
for( int i = 1; i < ind; i ++ ) cout << p[i] << ' ';↵
↵
if( id != -1 )↵
{↵
for( int i = id; i >= ind; i -- ) cout << p[i] << ' ';↵
for( int i = id + 1; i <= n; i ++ ) cout << p[i] << ' ';↵
}↵
cout << '\\n';↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:B,option1] Классная задача↵
- [likes:B,option2] Нормальная задача↵
- [likes:B,option3] Плохая задача↵
- [likes:B,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193C]↵
↵
- Идея: [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказка">↵
Для начала, попытаемся максимизировать все элементы $a$, а после ответим на запросы.↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Для начала, попытаемся максимизировать все элементы $a$, а после ответим на запросы. Переберем $i$ от $n$ до $1$ и приравняем $a_i$ к максимуму среди $a_i$, $b_i$ и $a_{i+1}$. Таким образом, каждый $a_i$ достигает максимального значения. Теперь мы можем написать префиксные суммы на массиве $a$, чтобы отвечать за $O(1)$ на каждый запрос.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
#define int long long↵
↵
using namespace std;↵
↵
signed main()↵
{↵
int t; cin >> t;↵
↵
while( t -- )↵
{↵
int n, q; cin >> n >> q;↵
int a[n + 5], b[n + 5], pref[n + 5], ans = 0;↵
↵
for( int i = 1; i <= n; i ++ ) cin >> a[i];↵
for( int i = 1; i <= n; i ++ ) cin >> b[i];↵
↵
a[n + 1] = 0;↵
↵
for( int i = n; i > 0; i -- ) a[i] = max({a[i], a[i + 1], b[i]});↵
↵
pref[0] = 0;↵
for( int i = 1; i <= n; i ++ ) pref[i] = pref[i - 1] + a[i];↵
↵
for( int i = 1; i <= q; i ++ ){↵
int L, R; cin >> L >> R;↵
cout << pref[R] - pref[L - 1] << " ";↵
}↵
cout << "\n";↵
}↵
}↵
```↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:C,option1] Классная задача↵
- [likes:C,option2] Нормальная задача↵
- [likes:C,option3] Плохая задача↵
- [likes:C,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193D]↵
↵
- Идея: [user:YF_YUSUF,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказки">↵
↵
<spoiler summary="Подсказка 1">↵
Чем больше сложность, тем меньше мечей можно использовать. Чем меньше мечей можно использовать, тем меньше уровней можно пройти.↵
</spoiler>↵
↵
↵
<spoiler summary="Подсказка 2">↵
Если оптимальная сложность равна $x$, то хотя бы один элемент в массиве $a$ равен $x$. В противном случае, мы бы могли увеличить $x$, не потеряв мечи.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Отсортируем все мечи по силе в порядке убывания. Тогда если сложность равна $a_i$, то количество мечей, которые можно использовать, равно $i$. По мере уменьшения сложности растет количество мечей, а значит и количество уровней, которые можно пройти. Можно поддерживать указатель на количество уровней и брать максимальный счет среди всех сложностей. Такое решение с указателем работает за $O(n)$ операций.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
↵
const int N = 2e5 + 12;↵
↵
int t, n, a[N], b[N];↵
↵
int main()↵
{↵
cin >> t;↵
↵
while( t -- )↵
{↵
cin >> n;↵
↵
for( int i = 1; i <= n; i ++ ) cin >> a[i];↵
for( int i = 1; i <= n; i ++ ) cin >> b[i];↵
↵
int h = 0, sum = 0; ll ans = 0;↵
sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);↵
↵
for( int i = 1; i <= n; i ++ )↵
{↵
while( h < n && sum + b[h + 1] <= i ) h ++, sum += b[h];↵
ans = max(ans, a[i] * 1ll * h);↵
}↵
cout << ans << '\n';↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:D,option1] Классная задача↵
- [likes:D,option2] Нормальная задача↵
- [likes:D,option3] Плохая задача↵
- [likes:D,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193E]↵
↵
- Идея: [user:Wansur,2026-01-25]↵
- Решение + разбор: [user:Wansur,2026-01-25]↵
↵
<spoiler summary="Подсказка">↵
Попробуйте дп подход к задаче.↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Будем писать динамику. $dp[x]$ это ответ для числа $x$. Изначально $dp[a_i] = 1$ для всех $i$ от $1$ до $n$, все остальные элементы $dp$ будут равны $10^9$. Переберем $x$ от $1$ до $n$ и рассмотрим переход:↵
↵
- Переберем все делители $y$ числа $x$.↵
- Обновим $dp[x]$ на $min(dp[x], dp[y] + dp[\frac{x}{y}])$.↵
↵
Заменим все $dp[x]$ равные $10^9$ на $-1$ и выведем все значения $dp$. В решении мы перебрали все числа от $1$ до $n$ и их делителей, суммарно это $O(n \log n)$ операций.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
const int maxn = 1'000'012;↵
↵
int a[maxn], dp[maxn];↵
int n, q;↵
↵
void solve() {↵
cin >> n;↵
↵
for(int i = 1; i <= n; i++) {↵
dp[i] = 1e9;↵
}↵
for(int i = 1; i <= n;i++) {↵
cin >> a[i];↵
dp[a[i]] = 1;↵
}↵
↵
for(int i = 1; i <= n; i++) {↵
for(int j = i; j <= n; j += i) {↵
dp[j] = min(dp[j], dp[i] + dp[j / i]);↵
}↵
}↵
↵
for(int i = 1; i <= n; i++) {↵
if(dp[i] == 1e9) {↵
dp[i] = -1;↵
}↵
cout << dp[i] << " \n"[i == n];↵
}↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t = 1;↵
cin >> t;↵
while(t--) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:E,option1] Классная задача↵
- [likes:E,option2] Нормальная задача↵
- [likes:E,option3] Плохая задача↵
- [likes:E,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193F]↵
↵
- Идея: [user:YF_YUSUF,2026-01-25], [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказки">↵
↵
<spoiler summary="Подсказка 1">↵
Для двух точек $(x_i, y_i)$ и $(x_j, y_j)$, если $x_i\lt x_j$, то доставить пиццу в точку $i$ нужно раньше, чем в точку $j$ (потому что из $(x, y)$ мы не можем пойти в $(x-1, y)$).↵
</spoiler>↵
↵
↵
<spoiler summary="Подсказка 2">↵
Попробуйте дп подход к задаче.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Разобьем точки доставки на группы с одинаковым $x_i$. Пронумеруем группы от $0$ до $m+1$ в порядке возрастания $x_i$, где $m$ это количество различных $x_i$. Группа $0$ это точка старта и группа $m+1$ это точка финиша.↵
↵
Поскольку мы не можем делать ходы влево, нужно доставить пиццу во все точки группы $i$, прежде чем перейти к группе $i+1$. Обозначим $high_i$ как точку с максимальным значением $y$ и $low_i$ как точку с минимальным значением $y$ в группе $i$. Поскольку все точки в группе находятся между ними, для группы, точкой куда доставят пиццу в последнюю очередь, окажется одна из них. Это означает, что переходить из группы $i$ в группу $i+1$ мы будем либо через $high_i$, либо через $low_i$.↵
↵
Теперь мы можем написать динамику на задачу. $dp[i][0]$ это минимальное количество времени для того, чтобы доставить пиццу во все группы от $0$ до $i$, последней доставив в точку $high_i$, и $dp[i][1]$ с точкой $low_i$ соответственно. Изначально, $dp[0][0] = 0$ и $dp[0][1] = 0$. Для всех других $i\gt 0$, переходы будут следующие:↵
↵
- $dp[i][0] = min(dp[i - 1][0] + dist(high_{i-1}, low_i), dp[i - 1][1] + dist(low_{i-1}, low_i)) + dist(low_i, high_i);$↵
- $dp[i][1] = min(dp[i - 1][0] + dist(high_{i-1}, high_i), dp[i - 1][1] + dist(low_{i-1}, high_i)) + dist(high_i, low_i);$↵
↵
Тут $dist(a, b)$ означает манхэттенское расстояние между точками $a$, $b$. Таким образом, на сортировку всех точек по группам уходит $O(n \log n)$ операций, а на подсчет динамики $O(n)$ операций.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
#define F first↵
#define S second↵
#define int long long↵
↵
using namespace std;↵
↵
int t, n, ax, ay, bx, by;↵
↵
signed main()↵
{↵
cin >> t;↵
↵
while( t -- )↵
{↵
cin >> n >> ax >> ay >> bx >> by;↵
vector <int> x(n + 5), y(n + 5), dp[2];↵
↵
dp[0] = dp[1] = vector <int> (n + 5, 0);↵
map <int, int> mx, mn;↵
↵
mn[ax] = mx[ax] = ay;↵
mn[bx] = mx[bx] = by;↵
↵
for( int i = 0; i < n; i ++ ) cin >> x[i];↵
for( int i = 0; i < n; i ++ ) cin >> y[i];↵
↵
for( int i = 0; i < n; i ++ )↵
{↵
mx[x[i]] = max(mx[x[i]], y[i]);↵
↵
if(!mn.count(x[i])) mn[x[i]] = y[i];↵
else mn[x[i]] = min(mn[x[i]], y[i]);↵
}↵
int lst = ax, cnt = 0;↵
↵
for( auto i : mx )↵
{↵
if( i.F == ax )↵
{↵
dp[0][0] = dp[1][0] = 0;↵
continue;↵
}↵
int need = (i.F - lst) + (mx[i.F] - mn[i.F]);↵
cnt ++;↵
↵
dp[0][cnt] = min(dp[0][cnt - 1] + abs(mx[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mx[i.F] - mx[lst])) + need;↵
dp[1][cnt] = min(dp[0][cnt - 1] + abs(mn[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mn[i.F] - mx[lst])) + need;↵
↵
lst = i.F;↵
}↵
cout << dp[0][cnt] << '\n';↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:F,option1] Классная задача↵
- [likes:F,option2] Нормальная задача↵
- [likes:F,option3] Плохая задача↵
- [likes:F,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193G]↵
↵
- Идея: [user:KluydQ,2026-01-25]↵
- Решение + разбор: [user:Wansur,2026-01-25], [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Подсказка">↵
Попробуйте разделить вершины по парам и запрашивать у интерактора эти пары.↵
</spoiler>↵
↵
↵
<spoiler summary="Решение">↵
Для начала, выпишем номера всех вершин дерева в последовательность $p$ в порядке обхода дфс. Разделим элементы последовательности $p$ по парам $(p_1, p_2)$, $(p_3, p_4)$ и так далее. Если $n$ нечетный, то временно забудем о последнем элементе.↵
↵
Переберем $i$ от 1 до $\frac{n}{2}$ и будем делать интерактору следующий запрос: $?$ $p_{2i-1}$ $p_{2i}$.↵
↵
- Если это две смежные вершины, то тогда, когда интерактор ответит $1$, мы будем однозначно знать, что хотя бы одна из вершин лежит на пути. В этом случае, мы можем за дополнительный запрос, узнать какая из двух вершин лежит на пути.↵
- Иначе, посмотрим на простой путь между двумя вершинами. Все пары до этой пары мы опросили, значит на их пути только они не были опрошены. Тогда, мы вернулись в ту же ситуацию, когда одна из вершин однозначно лежит на пути (если интерактор ответит положительно).↵
- Если мы нашли подходящую вершину, прекратим процесс.↵
↵
Когда $n$ нечетен, остается одна неопрошенная вершина. Если мы не нашли вершину из скрытого пути ни в одной паре, то однозначно можно сказать, что оставшаяся вершина и есть та, которая лежит на скрытом пути. В итоге мы получаем решение, которое работает ровно за $\lfloor\frac{n}{2}\rfloor$ + 1 запросов.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
#define sz(x) (int)(x.size())↵
#define pb push_back↵
↵
using namespace std; ↵
const int N = 2e5 + 12;↵
↵
int n, x, y, a, b;↵
vector <int> L, g[N];↵
↵
void dfs( int v, int p = 0 )↵
{↵
L.pb(v);↵
↵
for( auto to : g[v] )↵
{↵
if( to != p ) dfs(to, v);↵
}↵
}↵
int ask( int a, int b )↵
{↵
cout << "? " << a << ' ' << b << endl;↵
int res; cin >> res; return res;↵
}↵
void solve()↵
{↵
cin >> n;↵
↵
L.clear();↵
for( int i = 1; i <= n; i ++ ) g[i].clear();↵
↵
for( int i = 1; i < n; i ++ )↵
{↵
cin >> a >> b;↵
g[a].pb(b), g[b].pb(a);↵
}↵
dfs(1, 0);↵
↵
for( int i = 0; i < sz(L) - 1; i += 2 )↵
{↵
a = L[i], b = L[i + 1];↵
↵
if( ask(a, b) == 1 )↵
{↵
if( ask(a, a) == 1 ) cout << "! " << a << endl;↵
else cout << "! " << b << endl;↵
return;↵
}↵
}↵
cout << "! " << L.back() << endl;↵
}↵
int main()↵
{↵
int t; cin >> t;↵
while( t -- ) solve();↵
}↵
```↵
↵
## </spoiler>↵
↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:G,option1] Классная задача↵
- [likes:G,option2] Нормальная задача↵
- [likes:G,option3] Плохая задача↵
- [likes:G,option4] Не решил↵
↵
</spoiler>↵
↵
[problem:2193H]↵
↵
- Идея: [user:Mendeke,2026-01-25]↵
- Решение + разбор: [user:Wansur,2026-01-25], [user:China001,2026-01-25], [user:daki-sa,2026-01-25] и [user:KluydQ,2026-01-25]↵
↵
<spoiler summary="Основное решение">↵
Для начала возьмем все элементы по модулю $2$. Теперь все элементы равны единицам и нулям. Можно заметить, что если удалить все $a_i$, которые равны нулю, то $S_v$ для других не изменится. Удалим все $a_i$ равные нулю, у которых изначальный $S_v$ нечетен, если $S_v$ равен нулю, то ответа нет. Тех $v$, у которых $S_v$ четен, мы удаляем по мере удаления единиц.↵
↵
Теперь нужно разобраться с единицами. Всех $v$, у которых $a_v$ равен нулю, удалим из графа, оставив лес (граф из нескольких несвязных деревьев) из единиц. Решим задачу для каждого нового дерева из единиц. Для какого-то дерева из единиц размера $n$, ответа нет, когда $n$ четен. Когда $n$ четен, количество ребер нечетно, но каждое удаление удаляет одну вершину и четное количество ребер. Отнимая от изначального нечетного количество ребер четные числа, мы никогда не достигнем нуля ребер (то есть пустого графа). Теперь сделаем утверждение — когда $n$ нечетен, ответ есть всегда.↵
↵
Скажем, что для пары смежных вершин $(v, u)$, $v$ дает вклад в $u$ тогда, когда при удаление $u$, компонента вершины $v$ становится четного размера. Обозначим $f(v)$ как количество вершин, дающих вклад в $v$. Можно понять, что удалять нужно ту вершину, у которой $f(v)$ равен нулю. Компоненты всех соседей у такой вершины нечетного размера, а для получения нечетного $n$, нам нужно чтобы у нее было четное количество соседей (значит мы однозначно сможем удалить ее из графа). Теперь утверждается, что такая вершина всегда есть.↵
↵
<spoiler summary="Доказательство">↵
Рассмотрим какое-то ребро $(v, u)$ в дереве, поскольку $n$ нечетен, вклад дает либо $v$ в $u$, либо $u$ в $v$. Получается, сумма по всем $f(v)$ равна $n-1$, а значит по принципу Дирихле существует вершина, у которой $f(v)$ равен нулю, что и требовалось доказать.↵
</spoiler>↵
↵
Можно заметить, что после удаления вершины $v$, значения $f$ меняются только для соседей $v$. Для всех соседей $u$ вершины $v$ значение $f(u)$ уменьшается на $1$, ведь вклад давался из $v$ в $u$. Один раз посчитаем все значения $f$, и с помощью BFS будем удалять вершины, у которых значения $f$ равно нулю. Также не будем забывать, что некоторые нулю нужно удалить по мере удаления единиц. Это решение работает за O(n) операций.↵
</spoiler>↵
↵
↵
<spoiler summary="Второе решение">↵
Скажем, что корень дерева это вершина $1$. Будем писать динамику для задачи. Обозначим ее следующим образом:↵
↵
- $dp_v = 0$, если вершину $v$ удалить невозможно↵
- $dp_v = 1$, если для удаления вершины $v$, родитель вершины $v$ обязательно должен удаляться раньше вершины $v$.↵
- $dp_v = 2$, если для удаления вершины $v$, вершина $v$ обязательно должна удаляться раньше своего родителя.↵
- $dp_v = 3$, если для удаления вершины $v$ неважно, удалим мы родителя вершины или саму вершину первой.↵
↵
Если хотя бы для одного $v$, $dp_v$ равен нулю, то ответа не будет. Обозначим $p_v$ как родителя вершины $v$ и $s_v$ как сумму всех значений $a_u$, где $u$ это ребенок вершины $v$ и $dp_u$ равен $1$ или $3$. Для того, чтобы $dp_v$ был равен $1$, должно выполняться как минимум одно из двух условий:↵
↵
- $s_v$ по четности не равен $a_v$.↵
- $s_v$ по четности равен $a_v$, но у вершины есть ребенок $u$, для которого $dp_u = 3$ и $a_u = 1$. То есть, мы можем удалить $u$ раньше, чем $v$, тем самым изменив четность $s_v$.↵
↵
Прибавим $a_{p_v}$ к $s_v$ и проверим условия еще раз для $dp_v = 2$. Если в обоих случаях условия выполняются, то $dp_v = 3$, а если никакое не выполняется, то $dp_v = 0$. Осталось просто восстановить ответ по динамике, подробности можете посмотреть в реализации. Асимптотика решения — $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация основного решения">↵
↵
```↵
#include <bits/stdc++.h>↵
#define ent '\n'↵
#define int long long↵
↵
using namespace std;↵
const int maxn = 200'012;↵
const int mod = 1e9 + 7;↵
↵
int cnt[maxn], a[maxn], del[maxn];↵
int sz[maxn], bad[maxn], used[maxn];↵
vector<int> g[maxn], e[maxn], g2[maxn];↵
int n, m;↵
↵
void dfs(int v, int p) {↵
sz[v] = 1;↵
used[v] = true;↵
for(int to : g[v]) {↵
if(to == p) {↵
continue;↵
}↵
↵
dfs(to, v);↵
↵
if(sz[to] % 2 == 0) {↵
e[to].push_back(v);↵
bad[v]++;↵
}↵
else {↵
e[v].push_back(to);↵
bad[to]++;↵
}↵
↵
sz[v] += sz[to];↵
}↵
}↵
↵
void solve() {↵
cin >> n;↵
for(int i = 1; i <= n; i++) {↵
cin >> a[i];↵
a[i] %= 2;↵
del[i] = cnt[i] = sz[i] = 0;↵
bad[i] = used[i] = 0;↵
g[i].clear();↵
g2[i].clear();↵
e[i].clear();↵
}↵
↵
for(int i = 1; i < n; i++) {↵
int u, v;↵
cin >> u >> v;↵
↵
cnt[u] += a[v], cnt[v] += a[u];↵
↵
if(a[u] && a[v]) {↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
if( a[u] && !a[v] ) g2[u].push_back(v);↵
if( a[v] && !a[u] ) g2[v].push_back(u);↵
}↵
queue <int> q;↵
↵
for(int i = 1; i <= n; i++) {↵
if(!cnt[i] && !a[i]) {↵
cout << "NO\n";↵
return;↵
}↵
}↵
for(int i = 1; i <= n; i++) {↵
if(a[i] && !used[i]) {↵
dfs(i, 0);↵
if(sz[i] % 2 == 0) {↵
cout << "NO\n";↵
return;↵
}↵
}↵
}↵
for(int i = 1; i <= n; i++) {↵
if(a[i] && !bad[i]) {↵
q.push(i);↵
}↵
}↵
cout << "YES\n";↵
int zero[n + 5];↵
↵
for( int i = 1; i <= n; i ++ ){↵
zero[i] = 0;↵
↵
if( !a[i] && cnt[i] % 2 ) cout << i << ' ';↵
else if( !a[i] ) zero[i] = 1;↵
}↵
while(!q.empty()) {↵
int v = q.front(); q.pop();↵
cout << v << ' ';↵
for(int to : g2[v]){↵
if(zero[to]) cout << to << ' ', zero[to] = 0;↵
}↵
for(int to : e[v]) {↵
bad[to]--;↵
if(bad[to] == 0) q.push(to);↵
}↵
}↵
cout << ent;↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t = 1;↵
cin >> t;↵
while(t--) {↵
solve();↵
}↵
}↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Реализация второго решения">↵
↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
const int N = 2e5 + 12;↵
const int inf = 1e9 + 1;↵
↵
int n, x, y, a[N], dp[N], cnt[N], par[N];↵
vector <int> g[N], g2[N]; bool flag, used[N];↵
pair <int, int> must[N][3]; vector <int> ord;↵
↵
void dfs( int v, int p = 0 )↵
{↵
int s = 0, ok = 0, id = 0;↵
par[v] = p; ord.push_back(v);↵
↵
for( auto to : g[v] )↵
{↵
if( to == p ) continue;↵
↵
dfs(to, v);↵
if(!flag) return;↵
↵
if( dp[to] == 1 || dp[to] == 3 )↵
{↵
s ^= a[to];↵
↵
if( dp[to] == 3 && a[to] == 1 )↵
{↵
if( !ok )↵
{↵
ok = 1;↵
id = to;↵
}↵
}↵
if( dp[to] == 3 && id != to ) dp[to] = 1;↵
}↵
}↵
if( !ok && s == a[v] && (s + a[p]) % 2 == a[v] )↵
{↵
flag = 0;↵
return;↵
}↵
if( s != a[v] || ok )↵
{↵
if( s == a[v] ) must[v][1] = {id, 2};↵
else if(ok) must[v][1] = {id, 1};↵
↵
dp[v] = 1;↵
}↵
s = (s + a[p]) % 2;↵
↵
if( s != a[v] || ok )↵
{↵
if( s == a[v] ) must[v][2] = {id, 2};↵
else if(ok) must[v][2] = {id, 1};↵
↵
dp[v] += 2;↵
}↵
}↵
void dfs2( int v, int tp )↵
{↵
dp[v] = tp, used[v] = 1;↵
pair <int, int> p = must[v][tp];↵
if( p.first != 0 ) dfs2(p.first, p.second);↵
}↵
void solve()↵
{↵
cin >> n;↵
flag = 1;↵
↵
// dp[v] = 1, if p[v] before v↵
// dp[v] = 2, if v before p[v]↵
↵
for( int i = 1; i <= n; i ++ )↵
{↵
cin >> a[i];↵
a[i] %= 2;↵
↵
must[i][1] = must[i][2] = {0, 0};↵
dp[i] = cnt[i] = used[i] = 0;↵
g[i].clear(), g2[i].clear();↵
}↵
for( int i = 1; i < n; i ++ )↵
{↵
cin >> x >> y;↵
↵
g[x].push_back(y);↵
g[y].push_back(x);↵
}↵
ord.clear();↵
dfs(1);↵
↵
if( !flag )↵
{↵
cout << "No\n";↵
return;↵
}↵
cout << "Yes\n";↵
↵
for( auto i : ord )↵
{↵
if( !used[i] )↵
{↵
if( dp[i] == 3 ) dfs2(i, 1);↵
else dfs2(i, dp[i]);↵
}↵
}↵
for( int v = 2; v <= n; v ++ )↵
{↵
if( dp[v] == 1 ) cnt[v] ++, g2[par[v]].push_back(v);↵
else cnt[par[v]] ++, g2[v].push_back(par[v]);↵
}↵
queue <int> q;↵
↵
for( int i = 1; i <= n; i ++ )↵
{↵
if( cnt[i] == 0 ) q.push(i);↵
}↵
while( !q.empty() )↵
{↵
int v = q.front();↵
q.pop(); cout << v << ' ';↵
↵
for( auto to : g2[v] )↵
{↵
cnt[to] --;↵
if( !cnt[to] ) q.push(to);↵
}↵
}↵
cout << '\n';↵
}↵
int main()↵
{↵
ios_base::sync_with_stdio(0);↵
↵
int t; cin >> t;↵
while(t --) solve();↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Понравилась задача?">↵
↵
- [likes:H,option1] Классная задача↵
- [likes:H,option2] Нормальная задача↵
- [likes:H,option3] Плохая задача↵
- [likes:H,option4] Не решил↵
↵
</spoiler>↵
↵
