Друзья, окончательные результаты будут выложены завтра. ↵
↵
Мы уже проверили всех, кто набрал проходной балл (пока он не разглашается). Если ваши вердикты не изменились — это значит, что вы либо не набрали проходной балл, либо успешно прошли проверку на списывание. ↵
↵
Тем, кто получил вердикт «решение игнорировано»: напишите мне в личные сообщения до 16:00 по МСК 24.10, и мы обсудим вашу ситуацию с баном.↵
↵
Для справки: задачи 1-7 (A-G) относились к базовому треку, а задачи 4-10 (A-D-2G) — к углубленному.↵
↵
Ниже представлен разбор задач.↵
↵
---↵
↵
### A. Пара с суммой K↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Для каждого элемента массива достаточно знать, сколько раз среди уже просмотренных чисел встречается число, которое дополняет текущее до \(k\).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Заведите хэш-таблицу для подсчета частот и обновляйте ответ на лету, проходя по массиву один раз.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Поддерживаем словарь `cnt`, где `cnt[x]` — сколько раз число `x` уже встретилось. Проходим по массиву. Для текущего числа `a[i]` нам нужно найти `k - a[i]`. Если такое число уже было, добавляем к ответу `cnt[k - a[i]]`. После этого увеличиваем `cnt[a[i]]`. Так как ответ может достигать \(n(n-1)/2 \approx 2 \cdot 10^{10}\), используем 64-битный тип `long long`.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
long long k;↵
cin >> n >> k;↵
unordered_map<long long, long long> cnt;↵
long long ans = 0;↵
for (int i = 0; i < n; i+=1) {↵
long long x;↵
cin >> x;↵
ans += cnt[k - x];↵
cnt[x]++;↵
}↵
cout << ans;↵
}↵
~~~↵
</spoiler>↵
↵
### B. Минимум на отрезке↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
В задаче нет запросов на обновление, только запросы на чтение. Нам нужно быстро отвечать на вопрос «минимум на отрезке».↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Можно использовать разреженную таблицу (Sparse Table), которая позволяет отвечать на запрос за \(O(1)\) после \(O(n \log n)\) предподсчета, либо дерево отрезков.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Предподсчитаем `t[j][i]` — минимум на отрезке \([i, i + 2^j — 1]\). Для этого `t[0][i] = a[i]`, а `t[j][i] = min(t[j-1][i], t[j-1][i + 2^{j-1}])`. На запрос \([l, r]\) берем длину `d = r - l + 1`, находим максимальную степень двойки `j`. Ответ — `min(t[j][l], t[j][r - 2^j + 1])`.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++) cin >> a[i];↵
int k = 1;↵
while ((1 << k) <= n) k++;↵
vector<vector<int>> t(k, vector<int>(n));↵
for (int i = 0; i < n; i++) t[0][i] = a[i];↵
for (int j = 1; j < k; j++) {↵
for (int i = 0; i + (1 << j) <= n; i++) {↵
t[j][i] = min(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);↵
}↵
}↵
int q;↵
cin >> q;↵
while (q--) {↵
int l, r;↵
cin >> l >> r;↵
l--; r--;↵
↵
int d = r - l + 1;↵
int j = 31 - __builtin_clz(d);↵
cout << min(t[j][l], t[j][r - (1 << j) + 1]);↵
}↵
}↵
~~~↵
</spoiler>↵
↵
### C. Повышение по-начальски↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Запишите условие задачи в виде уравнения: \(a + x = m \cdot (b + x)\), где \(m\) — целое число \(> 1\).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Выразите \(x\). Вы поймете, что выражение \(b + x\) должно быть делителем разности \(a — b\).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Преобразуем уравнение: \(a + x = m(b + x) \Rightarrow a — b = (m — 1)(b + x)\). Обозначим \(d = m — 1\). Тогда \(b + x = (a — b) / d\). Значит, \(x = (a — b)/d — b\). Нам нужно перебрать все делители \(d\) числа \(a — b\), вычислить \(x\) и проверить, попадает ли он в отрезок \([l, r]\). Перебор делителей делается за \(O(\sqrt{a-b})\), что при \(a \le 10^{12}\) составит около \(10^6\) операций и спокойно уложится в лимит времени.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
long long a, b, l, r;↵
cin >> a >> b >> l >> r;↵
long long v = a - b, c = 0;↵
for (long long d = 1; d * d <= v; d++) {↵
if (v % d != 0) continue;↵
long long x = v / d - b;↵
if (x >= l && x <= r) c++;↵
long long d2 = v / d;↵
if (d2 != d) {↵
long long x2 = v / d2 - b;↵
if (x2 >= l && x2 <= r) c++;↵
}↵
}↵
cout << c;↵
}↵
~~~↵
</spoiler>↵
↵
### C. Повышение по-начальски↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Запишите условие задачи в виде уравнения: \(a + x = m \cdot (b + x)\), где \(m\) — целое число \(> 1\).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Выразите \(x\). Вы поймете, что выражение \(b + x\) должно быть делителем разности \(a — b\).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Преобразуем уравнение: \(a + x = m(b + x) \Rightarrow a — b = (m — 1)(b + x)\). Обозначим \(d = m — 1\). Тогда \(b + x = (a — b) / d\). Значит, \(x = (a — b)/d — b\). Нам нужно перебрать все делители \(d\) числа \(a — b\), вычислить \(x\) и проверить, попадает ли он в отрезок \([l, r]\). Перебор делителей делается за \(O(\sqrt{a-b})\), что при \(a \le 10^{12}\) составит около \(10^6\) операций и спокойно уложится в лимит времени.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
long long a, b, l, r;↵
cin >> a >> b >> l >> r;↵
long long v = a - b, c = 0;↵
for (long long d = 1; d * d <= v; d++) {↵
if (v % d != 0) continue;↵
long long x = v / d - b;↵
if (x >= l && x <= r) c++;↵
long long d2 = v / d;↵
if (d2 != d) {↵
long long x2 = v / d2 - b;↵
if (x2 >= l && x2 <= r) c++;↵
}↵
}↵
cout << c;↵
}↵
~~~↵
</spoiler>↵
↵
### E. Частоты на отрезке↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Задача на запросы к подотрезкам без обновлений. Для неё отлично подходит алгоритм Мо.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Для поддержки ответа используйте два массива: `c[x]` (сколько раз встречается число x) и `f[k]` (сколько чисел имеют частоту k). При добавлении или удалении элемента обновляйте оба счетчика за O(1).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Сортируем запросы по блокам (размер блока \(\sqrt{n}\)), четные блоки сортируем по возрастанию правой границы, нечетные — по убыванию. Двигаем указатели `cl` и `cr`. При сдвиге добавляем или убираем элемент. Если добавляем число `v`, текущая его частота была `x`. Мы делаем `f[x]--`, `c[v]++`, `f[x+1]++`. Аналогично при удалении. Ответ на запрос — просто `f[k]`.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
struct Q { int l, r, k, i; };↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n, q;↵
cin >> n >> q;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++) cin >> a[i];↵
vector<int> u = a;↵
sort(u.begin(), u.end());↵
u.erase(unique(u.begin(), u.end()), u.end());↵
for (int i = 0; i < n; i++) a[i] = lower_bound(u.begin(), u.end(), a[i]) - u.begin();↵
int m = u.size();↵
int b = max(1, (int)sqrt(n));↵
vector<Q> qs(q);↵
for (int i = 0; i < q; i++) {↵
cin >> qs[i].l >> qs[i].r >> qs[i].k;↵
qs[i].l--; qs[i].r--; qs[i].i = i;↵
}↵
sort(qs.begin(), qs.end(), [&](Q& x, Q& y) {↵
int bx = x.l / b, by = y.l / b;↵
if (bx != by) return bx < by;↵
if (bx & 1) return x.r > y.r;↵
return x.r < y.r;↵
});↵
vector<int> c(m, 0), f(n + 1, 0), ans(q);↵
int cl = 0, cr = -1;↵
for (auto& qu : qs) {↵
while (cl > qu.l) { cl--; int v = a[cl]; f[c[v]]--; c[v]++; f[c[v]]++; }↵
while (cr < qu.r) { cr++; int v = a[cr]; f[c[v]]--; c[v]++; f[c[v]]++; }↵
while (cl < qu.l) { int v = a[cl]; f[c[v]]--; c[v]--; f[c[v]]++; cl++; }↵
while (cr > qu.r) { int v = a[cr]; f[c[v]]--; c[v]--; f[c[v]]++; cr--; }↵
ans[qu.i] = (qu.k <= n ? f[qu.k] : 0);↵
}↵
for (int i = 0; i < q; i++) cout << ans[i] << '\n';↵
}↵
~~~↵
</spoiler>↵
↵
### F. Игра с циклом↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Несложно заметить, что первый игрок сделает \(\lceil n/2 \rceil\) ходов. При этом по итогу игры он заберет непрерывный кусок (дугу) на цикле ровно такой длины.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Второй игрок будет всячески мешать и отрежет ту дугу, которая даст минимальную сумму. Нам нужно найти максимум среди минимумов на всех окнах длины \(k = \lceil n/2 \rceil\).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Удвоим (или утроим) массив, чтобы линейно обрабатывать циклы. Посчитаем префиксные суммы. Для каждого возможного старта дуги длины \(k\) нам нужно найти ее сумму. Чтобы найти минимум на скользящем окне, используем монотонную очередь (deque) за \(O(n)\). Итоговый ответ первого игрока — максимум из этих минимумов. Ответ второго игрока — общая сумма всех элементов минус результат первого.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
cin >> n;↵
vector<long long> a(n);↵
long long s = 0;↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
s += a[i];↵
}↵
int k = (n + 1) / 2;↵
vector<long long> p(3 * n + 1, 0);↵
for (int i = 0; i < 3 * n; i++) p[i + 1] = p[i] + a[i % n];↵
vector<long long> b(2 * n + 1, 0);↵
for (int i = 0; i < 2 * n; i++) b[i] = p[i + k] - p[i];↵
deque<int> q;↵
long long m = -1e18;↵
for (int i = n - k + 1; i < 2 * n; i++) {↵
while (!q.empty() && q.front() < i - k + 1) q.pop_front();↵
while (!q.empty() && b[q.back()] >= b[i]) q.pop_back();↵
q.push_back(i);↵
if (i >= n) m = max(m, b[q.front()]);↵
}↵
cout << m << " " << s - m;↵
}↵
~~~↵
</spoiler>↵
↵
### G. Море парабол↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Для фиксированного \(x\) точка внутри всех парабол должна находиться между самой высокой параболой (с ветвями вверх) и самой низкой (с ветвями вниз).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Введем функцию \(g(x) = \max_{a_i > 0}(y_i) — \min_{a_i < 0}(y_i)\). Эта функция является выпуклой. Ее минимум можно найти тернарным поиском.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Если все параболы ветвями вверх — берем точку заведомо выше всех (по оси Y). Если вниз — заведомо ниже. Если есть и те, и другие — ищем минимум разности между верхней огибающей и нижней огибающей. Делаем 200 итераций тернарного поиска по \(x\) на отрезке \([-10^9, 10^9]\). В точке минимума проверяем, что `max_y < min_y`. Выводим середину интервала.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
cin >> n;↵
vector<long double> a(n), b(n), c(n);↵
bool hp = 0, hn = 0;↵
for (int i = 0; i < n; i++) {↵
cin >> a[i] >> b[i] >> c[i];↵
if (a[i] > 0) hp = 1;↵
else hn = 1;↵
}↵
if (!hn) {↵
long double mx = -1e30L;↵
for (int i = 0; i < n; i++) mx = max(mx, c[i]);↵
cout << fixed << setprecision(10) << 0.0L << " " << mx + 1;↵
} else if (!hp) {↵
long double mn = 1e30L;↵
for (int i = 0; i < n; i++) mn = min(mn, c[i]);↵
cout << fixed << setprecision(10) << 0.0L << " " << mn - 1;↵
} else {↵
auto f = [&](long double x) {↵
long double u = -1e30L, l = 1e30L;↵
for (int i = 0; i < n; i++) {↵
long double v = a[i] * x * x + b[i] * x + c[i];↵
if (a[i] > 0) u = max(u, v);↵
else l = min(l, v);↵
}↵
return u - l;↵
};↵
long double l = -1e9L, r = 1e9L;↵
for (int it = 0; it < 200; it++) {↵
long double m1 = l + (r - l) / 3;↵
long double m2 = r - (r - l) / 3;↵
if (f(m1) < f(m2)) r = m2;↵
else l = m1;↵
}↵
long double x = (l + r) / 2;↵
long double u = -1e30L, lo = 1e30L;↵
for (int i = 0; i < n; i++) {↵
long double v = a[i] * x * x + b[i] * x + c[i];↵
if (a[i] > 0) u = max(u, v);↵
else lo = min(lo, v);↵
}↵
cout << fixed << setprecision(10) << x << " " << (u + lo) / 2;↵
}↵
}↵
~~~↵
</spoiler>↵
↵
### 2E. Проверьте равенство↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Если \(a^b = c^d\), то можно привести \(a\) и \(c\) к некому общему основанию \(x\), то есть представить их в виде \(x^p\) и \(x^q\).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Тогда условие превращается в \(p \cdot b = q \cdot d\). Проблема в том, что \(b\) и \(d\) могут быть огромными (до \(10^{100}\)). Нужно использовать длинную арифметику или логарифмы.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Для начала определим знак результата. Если \(a < 0\) и \(b\) нечетное, то результат отрицательный, иначе положительный. Знаки \(a^b\) и \(c^d\) должны совпадать.↵
Далее нужно найти каноничное представление числа. Ищем максимальную степень \(p\), такую что \(a = x^p\). Это можно сделать, перебрав \(p\) от 64 до 2 (так как \(a \le 10^{100}\)) и проверив, является ли \(a\) точной \(p\)-й степенью (через бинарный поиск или `pow`).↵
Найдя \(p\) и \(q\), нам нужно проверить \(p \cdot b = q \cdot d\). Поскольку \(p\) и \(q\) малы, а \(b\) и \(d\) огромны, мы можем просто умножить строки на эти числа и сравнить результаты.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
string mul(string s, int x) {↵
if (s == "0" || x == 0) return "0";↵
string r;↵
int c = 0;↵
for (int i = s.size() - 1; i >= 0 || c; i--) {↵
int v = c;↵
if (i >= 0) v += (s[i] - '0') * x;↵
r += char('0' + v % 10);↵
c = v / 10;↵
}↵
reverse(r.begin(), r.end());↵
return r;↵
}↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
string a, b, c, d;↵
cin >> a >> b >> c >> d;↵
bool na = a[0] == '-', nc = c[0] == '-';↵
if (na) a = a.substr(1);↵
if (nc) c = c.substr(1);↵
if (((b.back() - '0') % 2 && na) != ((d.back() - '0') % 2 && nc)) {↵
cout << "incorrect";↵
return;↵
}↵
if (a == "1" || c == "1") {↵
if (a == "1" && c == "1") cout << "correct";↵
else cout << "incorrect";↵
return;↵
}↵
auto f = [&](string s) {↵
long double v = 0;↵
for (char ch : s) v = v * 10 + (ch - '0');↵
for (int p = 64; p >= 2; p--) {↵
long long r = round(pow(v, 1.0L / p));↵
if (r < 2) continue;↵
long long cur = 1;↵
bool of = 0;↵
for (int i = 0; i < p; i++) {↵
if (cur > 1000000000000000000LL / r) { of = 1; break; }↵
cur *= r;↵
}↵
if (!of && to_string(cur) == s) return make_pair(r, p);↵
}↵
return make_pair((long long)v, 1);↵
};↵
auto x = f(a), y = f(c);↵
if (x.first != y.first) {↵
cout << "incorrect";↵
return;↵
}↵
cout << (mul(b, x.second) == mul(d, y.second) ? "correct" : "incorrect");↵
}↵
~~~↵
</spoiler>↵
↵
### 2F. Сумма расстояний↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Если зафиксировать корень в вершине 1, можно легко посчитать суммы расстояний от нее до всех остальных вершин с помощью одного обхода в глубину.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Чтобы не пересчитывать все заново, используйте технику переподвешивания (Rerooting DP). При переходе от родителя к ребенку расстояния до вершин в его поддереве уменьшаются на \(w\), а до всех остальных — увеличиваются на \(w\). Не забудьте использовать 128-битный тип для ответа.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Сначала считаем размеры поддеревьев `s[v]` и сумму расстояний `a[v]` от корня до вершин в его поддереве. Затем делаем второй обход. Если мы знаем ответ для вершины `u`, то для ее ребенка `v`, соединенного ребром веса `w`, ответ считается как: `b[v] = b[u] - s[v] * w + (n - s[v]) * w = b[u] + (n - 2 * s[v]) * w`. Ответы могут достигать \(10^{19}\), поэтому используйте `__int128`.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
void pr(__int128 x) {↵
if (x == 0) { cout << 0; return; }↵
string s;↵
while (x > 0) { s += (char)('0' + (x % 10)); x /= 10; }↵
reverse(s.begin(), s.end());↵
cout << s;↵
}↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
cin >> n;↵
vector<vector<pair<int, long long>>> g(n);↵
for (int i = 0; i < n - 1; i++) {↵
int u, v;↵
long long w;↵
cin >> u >> v >> w;↵
u--; v--;↵
g[u].push_back({v, w});↵
g[v].push_back({u, w});↵
}↵
vector<int> p(n, -1), o;↵
vector<long long> pw(n, 0);↵
p[0] = -2;↵
vector<int> st = {0};↵
while (!st.empty()) {↵
int v = st.back();↵
st.pop_back();↵
o.push_back(v);↵
for (auto [to, w] : g[v]) {↵
if (p[to] == -1) {↵
p[to] = v;↵
pw[to] = w;↵
st.push_back(to);↵
}↵
}↵
}↵
vector<long long> s(n, 1);↵
vector<__int128> a(n, 0), b(n, 0);↵
for (int i = n - 1; i >= 0; i--) {↵
int v = o[i];↵
if (p[v] == -2) continue;↵
s[p[v]] += s[v];↵
a[p[v]] += a[v] + (__int128)s[v] * pw[v];↵
}↵
b[0] = a[0];↵
for (int i = 1; i < n; i++) {↵
int v = o[i];↵
b[v] = b[p[v]] + (__int128)(n - 2 * s[v]) * pw[v];↵
}↵
for (int i = 0; i < n; i++) {↵
if (i) cout << " ";↵
pr(b[i]);↵
}↵
}↵
~~~↵
</spoiler>↵
↵
### 2G. Пути на дереве↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Нужно посчитать количество путей с заданной суммой на дереве. Это классическая задача, которая эффективно решается с помощью центроидной декомпозиции.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Каждый раз, когда мы находим центроид, мы считаем все пути, проходящие через него (используя сортировку и два указателя). Чтобы не посчитать лишнего, вычитаем пути, которые целиком лежат в одном поддереве.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Находим центроид текущего дерева. Для него собираем расстояния от всех вершин в его компоненте. Сортируем этот список и двумя указателями считаем количество пар с суммой \(K\). Затем для каждого поддерева центроида собираем расстояния только внутри этого поддерева, сортируем и вычитаем такие же пары (чтобы не учитывать пути, не проходящие через центроид). После этого удаляем центроид и рекурсивно запускаемся от его соседей. Сложность \(O(n \log^2 n)\).↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int n;↵
long long k;↵
vector<vector<pair<int,long long>>> g;↵
vector<int> s;↵
vector<bool> r;↵
long long a = 0;↵
void sz(int v, int p) {↵
s[v] = 1;↵
for (auto [u, w] : g[v]) {↵
if (u != p && !r[u]) {↵
sz(u, v);↵
s[v] += s[u];↵
}↵
}↵
}↵
int ct(int v, int p, int t) {↵
for (auto [u, w] : g[v]) {↵
if (u != p && !r[u] && s[u] > t / 2) return ct(u, v, t);↵
}↵
return v;↵
}↵
void cd(int v, int p, long long d, vector<long long>& o) {↵
o.push_back(d);↵
for (auto [u, w] : g[v]) {↵
if (u != p && !r[u]) cd(u, v, d + w, o);↵
}↵
}↵
long long cp(vector<long long>& v) {↵
sort(v.begin(), v.end());↵
long long c = 0;↵
int l = 0, r = (int)v.size() - 1;↵
while (l < r) {↵
long long sm = v[l] + v[r];↵
if (sm == k) {↵
if (v[l] == v[r]) {↵
long long x = r - l + 1;↵
c += x * (x - 1) / 2;↵
break;↵
}↵
long long cl = 1, cr = 1;↵
while (l + 1 < r && v[l] == v[l + 1]) { l++; cl++; }↵
while (r - 1 > l && v[r] == v[r - 1]) { r--; cr++; }↵
c += cl * cr;↵
l++; r--;↵
} else if (sm < k) l++;↵
else r--;↵
}↵
return c;↵
}↵
void dc(int v) {↵
sz(v, -1);↵
int c = ct(v, -1, s[v]);↵
vector<long long> o;↵
o.push_back(0);↵
for (auto [u, w] : g[c]) {↵
if (!r[u]) {↵
vector<long long> b;↵
cd(u, c, w, b);↵
a -= cp(b);↵
for (auto d : b) o.push_back(d);↵
}↵
}↵
a += cp(o);↵
r[c] = true;↵
for (auto [u, w] : g[c]) {↵
if (!r[u]) dc(u);↵
}↵
}↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cin >> n >> k;↵
g.resize(n);↵
for (int i = 0; i < n - 1; i++) {↵
int u, v;↵
long long w;↵
cin >> u >> v >> w;↵
u--; v--;↵
g[u].push_back({v, w});↵
g[v].push_back({u, w});↵
}↵
s.assign(n, 0);↵
r.assign(n, false);↵
dc(0);↵
cout << a;↵
}↵
~~~↵
</spoiler>↵
↵
Спасибо за участие!!! Мы приносим прощения если что-то было не так, хотелось отметить что проверку на ИИ делало ИИ, а затем человек, поэтому могут быть ошибки. Прямо сейчас мы открываем доступ к чужим посылкам, если вы заметили ИИ, то пожалуйста, сообщите об этом [user:Arbuzik342,2026-10-23] с добавлением причин почему вы так считаете. ↵
↵
P.S. Мои навыки английского не так хороши да и перевести столько я не смогу без потери точности, может ли кто-то помочь мне в этом?
↵
Мы уже проверили всех, кто набрал проходной балл (пока он не разглашается). Если ваши вердикты не изменились — это значит, что вы либо не набрали проходной балл, либо успешно прошли проверку на списывание. ↵
↵
Тем, кто получил вердикт «решение игнорировано»: напишите мне в личные сообщения до 16:00 по МСК 24.10, и мы обсудим вашу ситуацию с баном.↵
↵
Для справки: задачи 1-7 (A-G) относились к базовому треку, а задачи 4-10 (
↵
Ниже представлен разбор задач.↵
↵
---↵
↵
### A. Пара с суммой K↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Для каждого элемента массива достаточно знать, сколько раз среди уже просмотренных чисел встречается число, которое дополняет текущее до \(k\).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Заведите хэш-таблицу для подсчета частот и обновляйте ответ на лету, проходя по массиву один раз.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Поддерживаем словарь `cnt`, где `cnt[x]` — сколько раз число `x` уже встретилось. Проходим по массиву. Для текущего числа `a[i]` нам нужно найти `k - a[i]`. Если такое число уже было, добавляем к ответу `cnt[k - a[i]]`. После этого увеличиваем `cnt[a[i]]`. Так как ответ может достигать \(n(n-1)/2 \approx 2 \cdot 10^{10}\), используем 64-битный тип `long long`.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
long long k;↵
cin >> n >> k;↵
unordered_map<long long, long long> cnt;↵
long long ans = 0;↵
for (int i = 0; i < n; i+=1) {↵
long long x;↵
cin >> x;↵
ans += cnt[k - x];↵
cnt[x]++;↵
}↵
cout << ans;↵
}↵
~~~↵
</spoiler>↵
↵
### B. Минимум на отрезке↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
В задаче нет запросов на обновление, только запросы на чтение. Нам нужно быстро отвечать на вопрос «минимум на отрезке».↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Можно использовать разреженную таблицу (Sparse Table), которая позволяет отвечать на запрос за \(O(1)\) после \(O(n \log n)\) предподсчета, либо дерево отрезков.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Предподсчитаем `t[j][i]` — минимум на отрезке \([i, i + 2^j — 1]\). Для этого `t[0][i] = a[i]`, а `t[j][i] = min(t[j-1][i], t[j-1][i + 2^{j-1}])`. На запрос \([l, r]\) берем длину `d = r - l + 1`, находим максимальную степень двойки `j`. Ответ — `min(t[j][l], t[j][r - 2^j + 1])`.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++) cin >> a[i];↵
int k = 1;↵
while ((1 << k) <= n) k++;↵
vector<vector<int>> t(k, vector<int>(n));↵
for (int i = 0; i < n; i++) t[0][i] = a[i];↵
for (int j = 1; j < k; j++) {↵
for (int i = 0; i + (1 << j) <= n; i++) {↵
t[j][i] = min(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);↵
}↵
}↵
int q;↵
cin >> q;↵
while (q--) {↵
int l, r;↵
cin >> l >> r;↵
l--; r--;↵
↵
int d = r - l + 1;↵
int j = 31 - __builtin_clz(d);↵
cout << min(t[j][l], t[j][r - (1 << j) + 1]);↵
}↵
}↵
~~~↵
</spoiler>↵
↵
### C. Повышение по-начальски↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Запишите условие задачи в виде уравнения: \(a + x = m \cdot (b + x)\), где \(m\) — целое число \(> 1\).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Выразите \(x\). Вы поймете, что выражение \(b + x\) должно быть делителем разности \(a — b\).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Преобразуем уравнение: \(a + x = m(b + x) \Rightarrow a — b = (m — 1)(b + x)\). Обозначим \(d = m — 1\). Тогда \(b + x = (a — b) / d\). Значит, \(x = (a — b)/d — b\). Нам нужно перебрать все делители \(d\) числа \(a — b\), вычислить \(x\) и проверить, попадает ли он в отрезок \([l, r]\). Перебор делителей делается за \(O(\sqrt{a-b})\), что при \(a \le 10^{12}\) составит около \(10^6\) операций и спокойно уложится в лимит времени.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
long long a, b, l, r;↵
cin >> a >> b >> l >> r;↵
long long v = a - b, c = 0;↵
for (long long d = 1; d * d <= v; d++) {↵
if (v % d != 0) continue;↵
long long x = v / d - b;↵
if (x >= l && x <= r) c++;↵
long long d2 = v / d;↵
if (d2 != d) {↵
long long x2 = v / d2 - b;↵
if (x2 >= l && x2 <= r) c++;↵
}↵
}↵
cout << c;↵
}↵
~~~↵
</spoiler>↵
↵
### C. Повышение по-начальски↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Запишите условие задачи в виде уравнения: \(a + x = m \cdot (b + x)\), где \(m\) — целое число \(> 1\).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Выразите \(x\). Вы поймете, что выражение \(b + x\) должно быть делителем разности \(a — b\).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Преобразуем уравнение: \(a + x = m(b + x) \Rightarrow a — b = (m — 1)(b + x)\). Обозначим \(d = m — 1\). Тогда \(b + x = (a — b) / d\). Значит, \(x = (a — b)/d — b\). Нам нужно перебрать все делители \(d\) числа \(a — b\), вычислить \(x\) и проверить, попадает ли он в отрезок \([l, r]\). Перебор делителей делается за \(O(\sqrt{a-b})\), что при \(a \le 10^{12}\) составит около \(10^6\) операций и спокойно уложится в лимит времени.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
long long a, b, l, r;↵
cin >> a >> b >> l >> r;↵
long long v = a - b, c = 0;↵
for (long long d = 1; d * d <= v; d++) {↵
if (v % d != 0) continue;↵
long long x = v / d - b;↵
if (x >= l && x <= r) c++;↵
long long d2 = v / d;↵
if (d2 != d) {↵
long long x2 = v / d2 - b;↵
if (x2 >= l && x2 <= r) c++;↵
}↵
}↵
cout << c;↵
}↵
~~~↵
</spoiler>↵
↵
### E. Частоты на отрезке↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Задача на запросы к подотрезкам без обновлений. Для неё отлично подходит алгоритм Мо.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Для поддержки ответа используйте два массива: `c[x]` (сколько раз встречается число x) и `f[k]` (сколько чисел имеют частоту k). При добавлении или удалении элемента обновляйте оба счетчика за O(1).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Сортируем запросы по блокам (размер блока \(\sqrt{n}\)), четные блоки сортируем по возрастанию правой границы, нечетные — по убыванию. Двигаем указатели `cl` и `cr`. При сдвиге добавляем или убираем элемент. Если добавляем число `v`, текущая его частота была `x`. Мы делаем `f[x]--`, `c[v]++`, `f[x+1]++`. Аналогично при удалении. Ответ на запрос — просто `f[k]`.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
struct Q { int l, r, k, i; };↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n, q;↵
cin >> n >> q;↵
vector<int> a(n);↵
for (int i = 0; i < n; i++) cin >> a[i];↵
vector<int> u = a;↵
sort(u.begin(), u.end());↵
u.erase(unique(u.begin(), u.end()), u.end());↵
for (int i = 0; i < n; i++) a[i] = lower_bound(u.begin(), u.end(), a[i]) - u.begin();↵
int m = u.size();↵
int b = max(1, (int)sqrt(n));↵
vector<Q> qs(q);↵
for (int i = 0; i < q; i++) {↵
cin >> qs[i].l >> qs[i].r >> qs[i].k;↵
qs[i].l--; qs[i].r--; qs[i].i = i;↵
}↵
sort(qs.begin(), qs.end(), [&](Q& x, Q& y) {↵
int bx = x.l / b, by = y.l / b;↵
if (bx != by) return bx < by;↵
if (bx & 1) return x.r > y.r;↵
return x.r < y.r;↵
});↵
vector<int> c(m, 0), f(n + 1, 0), ans(q);↵
int cl = 0, cr = -1;↵
for (auto& qu : qs) {↵
while (cl > qu.l) { cl--; int v = a[cl]; f[c[v]]--; c[v]++; f[c[v]]++; }↵
while (cr < qu.r) { cr++; int v = a[cr]; f[c[v]]--; c[v]++; f[c[v]]++; }↵
while (cl < qu.l) { int v = a[cl]; f[c[v]]--; c[v]--; f[c[v]]++; cl++; }↵
while (cr > qu.r) { int v = a[cr]; f[c[v]]--; c[v]--; f[c[v]]++; cr--; }↵
ans[qu.i] = (qu.k <= n ? f[qu.k] : 0);↵
}↵
for (int i = 0; i < q; i++) cout << ans[i] << '\n';↵
}↵
~~~↵
</spoiler>↵
↵
### F. Игра с циклом↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Несложно заметить, что первый игрок сделает \(\lceil n/2 \rceil\) ходов. При этом по итогу игры он заберет непрерывный кусок (дугу) на цикле ровно такой длины.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Второй игрок будет всячески мешать и отрежет ту дугу, которая даст минимальную сумму. Нам нужно найти максимум среди минимумов на всех окнах длины \(k = \lceil n/2 \rceil\).↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Удвоим (или утроим) массив, чтобы линейно обрабатывать циклы. Посчитаем префиксные суммы. Для каждого возможного старта дуги длины \(k\) нам нужно найти ее сумму. Чтобы найти минимум на скользящем окне, используем монотонную очередь (deque) за \(O(n)\). Итоговый ответ первого игрока — максимум из этих минимумов. Ответ второго игрока — общая сумма всех элементов минус результат первого.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
cin >> n;↵
vector<long long> a(n);↵
long long s = 0;↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
s += a[i];↵
}↵
int k = (n + 1) / 2;↵
vector<long long> p(3 * n + 1, 0);↵
for (int i = 0; i < 3 * n; i++) p[i + 1] = p[i] + a[i % n];↵
vector<long long> b(2 * n + 1, 0);↵
for (int i = 0; i < 2 * n; i++) b[i] = p[i + k] - p[i];↵
deque<int> q;↵
long long m = -1e18;↵
for (int i = n - k + 1; i < 2 * n; i++) {↵
while (!q.empty() && q.front() < i - k + 1) q.pop_front();↵
while (!q.empty() && b[q.back()] >= b[i]) q.pop_back();↵
q.push_back(i);↵
if (i >= n) m = max(m, b[q.front()]);↵
}↵
cout << m << " " << s - m;↵
}↵
~~~↵
</spoiler>↵
↵
### G. Море парабол↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Для фиксированного \(x\) точка внутри всех парабол должна находиться между самой высокой параболой (с ветвями вверх) и самой низкой (с ветвями вниз).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Введем функцию \(g(x) = \max_{a_i > 0}(y_i) — \min_{a_i < 0}(y_i)\). Эта функция является выпуклой. Ее минимум можно найти тернарным поиском.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Если все параболы ветвями вверх — берем точку заведомо выше всех (по оси Y). Если вниз — заведомо ниже. Если есть и те, и другие — ищем минимум разности между верхней огибающей и нижней огибающей. Делаем 200 итераций тернарного поиска по \(x\) на отрезке \([-10^9, 10^9]\). В точке минимума проверяем, что `max_y < min_y`. Выводим середину интервала.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
cin >> n;↵
vector<long double> a(n), b(n), c(n);↵
bool hp = 0, hn = 0;↵
for (int i = 0; i < n; i++) {↵
cin >> a[i] >> b[i] >> c[i];↵
if (a[i] > 0) hp = 1;↵
else hn = 1;↵
}↵
if (!hn) {↵
long double mx = -1e30L;↵
for (int i = 0; i < n; i++) mx = max(mx, c[i]);↵
cout << fixed << setprecision(10) << 0.0L << " " << mx + 1;↵
} else if (!hp) {↵
long double mn = 1e30L;↵
for (int i = 0; i < n; i++) mn = min(mn, c[i]);↵
cout << fixed << setprecision(10) << 0.0L << " " << mn - 1;↵
} else {↵
auto f = [&](long double x) {↵
long double u = -1e30L, l = 1e30L;↵
for (int i = 0; i < n; i++) {↵
long double v = a[i] * x * x + b[i] * x + c[i];↵
if (a[i] > 0) u = max(u, v);↵
else l = min(l, v);↵
}↵
return u - l;↵
};↵
long double l = -1e9L, r = 1e9L;↵
for (int it = 0; it < 200; it++) {↵
long double m1 = l + (r - l) / 3;↵
long double m2 = r - (r - l) / 3;↵
if (f(m1) < f(m2)) r = m2;↵
else l = m1;↵
}↵
long double x = (l + r) / 2;↵
long double u = -1e30L, lo = 1e30L;↵
for (int i = 0; i < n; i++) {↵
long double v = a[i] * x * x + b[i] * x + c[i];↵
if (a[i] > 0) u = max(u, v);↵
else lo = min(lo, v);↵
}↵
cout << fixed << setprecision(10) << x << " " << (u + lo) / 2;↵
}↵
}↵
~~~↵
</spoiler>↵
↵
### 2E. Проверьте равенство↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Если \(a^b = c^d\), то можно привести \(a\) и \(c\) к некому общему основанию \(x\), то есть представить их в виде \(x^p\) и \(x^q\).↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Тогда условие превращается в \(p \cdot b = q \cdot d\). Проблема в том, что \(b\) и \(d\) могут быть огромными (до \(10^{100}\)). Нужно использовать длинную арифметику или логарифмы.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Для начала определим знак результата. Если \(a < 0\) и \(b\) нечетное, то результат отрицательный, иначе положительный. Знаки \(a^b\) и \(c^d\) должны совпадать.↵
Далее нужно найти каноничное представление числа. Ищем максимальную степень \(p\), такую что \(a = x^p\). Это можно сделать, перебрав \(p\) от 64 до 2 (так как \(a \le 10^{100}\)) и проверив, является ли \(a\) точной \(p\)-й степенью (через бинарный поиск или `pow`).↵
Найдя \(p\) и \(q\), нам нужно проверить \(p \cdot b = q \cdot d\). Поскольку \(p\) и \(q\) малы, а \(b\) и \(d\) огромны, мы можем просто умножить строки на эти числа и сравнить результаты.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
string mul(string s, int x) {↵
if (s == "0" || x == 0) return "0";↵
string r;↵
int c = 0;↵
for (int i = s.size() - 1; i >= 0 || c; i--) {↵
int v = c;↵
if (i >= 0) v += (s[i] - '0') * x;↵
r += char('0' + v % 10);↵
c = v / 10;↵
}↵
reverse(r.begin(), r.end());↵
return r;↵
}↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
string a, b, c, d;↵
cin >> a >> b >> c >> d;↵
bool na = a[0] == '-', nc = c[0] == '-';↵
if (na) a = a.substr(1);↵
if (nc) c = c.substr(1);↵
if (((b.back() - '0') % 2 && na) != ((d.back() - '0') % 2 && nc)) {↵
cout << "incorrect";↵
return;↵
}↵
if (a == "1" || c == "1") {↵
if (a == "1" && c == "1") cout << "correct";↵
else cout << "incorrect";↵
return;↵
}↵
auto f = [&](string s) {↵
long double v = 0;↵
for (char ch : s) v = v * 10 + (ch - '0');↵
for (int p = 64; p >= 2; p--) {↵
long long r = round(pow(v, 1.0L / p));↵
if (r < 2) continue;↵
long long cur = 1;↵
bool of = 0;↵
for (int i = 0; i < p; i++) {↵
if (cur > 1000000000000000000LL / r) { of = 1; break; }↵
cur *= r;↵
}↵
if (!of && to_string(cur) == s) return make_pair(r, p);↵
}↵
return make_pair((long long)v, 1);↵
};↵
auto x = f(a), y = f(c);↵
if (x.first != y.first) {↵
cout << "incorrect";↵
return;↵
}↵
cout << (mul(b, x.second) == mul(d, y.second) ? "correct" : "incorrect");↵
}↵
~~~↵
</spoiler>↵
↵
### 2F. Сумма расстояний↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Если зафиксировать корень в вершине 1, можно легко посчитать суммы расстояний от нее до всех остальных вершин с помощью одного обхода в глубину.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Чтобы не пересчитывать все заново, используйте технику переподвешивания (Rerooting DP). При переходе от родителя к ребенку расстояния до вершин в его поддереве уменьшаются на \(w\), а до всех остальных — увеличиваются на \(w\). Не забудьте использовать 128-битный тип для ответа.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Сначала считаем размеры поддеревьев `s[v]` и сумму расстояний `a[v]` от корня до вершин в его поддереве. Затем делаем второй обход. Если мы знаем ответ для вершины `u`, то для ее ребенка `v`, соединенного ребром веса `w`, ответ считается как: `b[v] = b[u] - s[v] * w + (n - s[v]) * w = b[u] + (n - 2 * s[v]) * w`. Ответы могут достигать \(10^{19}\), поэтому используйте `__int128`.↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
void pr(__int128 x) {↵
if (x == 0) { cout << 0; return; }↵
string s;↵
while (x > 0) { s += (char)('0' + (x % 10)); x /= 10; }↵
reverse(s.begin(), s.end());↵
cout << s;↵
}↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
int n;↵
cin >> n;↵
vector<vector<pair<int, long long>>> g(n);↵
for (int i = 0; i < n - 1; i++) {↵
int u, v;↵
long long w;↵
cin >> u >> v >> w;↵
u--; v--;↵
g[u].push_back({v, w});↵
g[v].push_back({u, w});↵
}↵
vector<int> p(n, -1), o;↵
vector<long long> pw(n, 0);↵
p[0] = -2;↵
vector<int> st = {0};↵
while (!st.empty()) {↵
int v = st.back();↵
st.pop_back();↵
o.push_back(v);↵
for (auto [to, w] : g[v]) {↵
if (p[to] == -1) {↵
p[to] = v;↵
pw[to] = w;↵
st.push_back(to);↵
}↵
}↵
}↵
vector<long long> s(n, 1);↵
vector<__int128> a(n, 0), b(n, 0);↵
for (int i = n - 1; i >= 0; i--) {↵
int v = o[i];↵
if (p[v] == -2) continue;↵
s[p[v]] += s[v];↵
a[p[v]] += a[v] + (__int128)s[v] * pw[v];↵
}↵
b[0] = a[0];↵
for (int i = 1; i < n; i++) {↵
int v = o[i];↵
b[v] = b[p[v]] + (__int128)(n - 2 * s[v]) * pw[v];↵
}↵
for (int i = 0; i < n; i++) {↵
if (i) cout << " ";↵
pr(b[i]);↵
}↵
}↵
~~~↵
</spoiler>↵
↵
### 2G. Пути на дереве↵
↵
**Idea:** [user:Arbuzik342,2026-10-18]↵
**Preparation:** [user:Arbuzik342,2026-10-18], [user:zeyd1234,2026-10-18]↵
↵
<spoiler summary="Подсказка 1">↵
Нужно посчитать количество путей с заданной суммой на дереве. Это классическая задача, которая эффективно решается с помощью центроидной декомпозиции.↵
</spoiler>↵
↵
<spoiler summary="Подсказка 2">↵
Каждый раз, когда мы находим центроид, мы считаем все пути, проходящие через него (используя сортировку и два указателя). Чтобы не посчитать лишнего, вычитаем пути, которые целиком лежат в одном поддереве.↵
</spoiler>↵
↵
<spoiler summary="Решение">↵
Находим центроид текущего дерева. Для него собираем расстояния от всех вершин в его компоненте. Сортируем этот список и двумя указателями считаем количество пар с суммой \(K\). Затем для каждого поддерева центроида собираем расстояния только внутри этого поддерева, сортируем и вычитаем такие же пары (чтобы не учитывать пути, не проходящие через центроид). После этого удаляем центроид и рекурсивно запускаемся от его соседей. Сложность \(O(n \log^2 n)\).↵
</spoiler>↵
↵
<spoiler summary="Код">↵
~~~cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
int n;↵
long long k;↵
vector<vector<pair<int,long long>>> g;↵
vector<int> s;↵
vector<bool> r;↵
long long a = 0;↵
void sz(int v, int p) {↵
s[v] = 1;↵
for (auto [u, w] : g[v]) {↵
if (u != p && !r[u]) {↵
sz(u, v);↵
s[v] += s[u];↵
}↵
}↵
}↵
int ct(int v, int p, int t) {↵
for (auto [u, w] : g[v]) {↵
if (u != p && !r[u] && s[u] > t / 2) return ct(u, v, t);↵
}↵
return v;↵
}↵
void cd(int v, int p, long long d, vector<long long>& o) {↵
o.push_back(d);↵
for (auto [u, w] : g[v]) {↵
if (u != p && !r[u]) cd(u, v, d + w, o);↵
}↵
}↵
long long cp(vector<long long>& v) {↵
sort(v.begin(), v.end());↵
long long c = 0;↵
int l = 0, r = (int)v.size() - 1;↵
while (l < r) {↵
long long sm = v[l] + v[r];↵
if (sm == k) {↵
if (v[l] == v[r]) {↵
long long x = r - l + 1;↵
c += x * (x - 1) / 2;↵
break;↵
}↵
long long cl = 1, cr = 1;↵
while (l + 1 < r && v[l] == v[l + 1]) { l++; cl++; }↵
while (r - 1 > l && v[r] == v[r - 1]) { r--; cr++; }↵
c += cl * cr;↵
l++; r--;↵
} else if (sm < k) l++;↵
else r--;↵
}↵
return c;↵
}↵
void dc(int v) {↵
sz(v, -1);↵
int c = ct(v, -1, s[v]);↵
vector<long long> o;↵
o.push_back(0);↵
for (auto [u, w] : g[c]) {↵
if (!r[u]) {↵
vector<long long> b;↵
cd(u, c, w, b);↵
a -= cp(b);↵
for (auto d : b) o.push_back(d);↵
}↵
}↵
a += cp(o);↵
r[c] = true;↵
for (auto [u, w] : g[c]) {↵
if (!r[u]) dc(u);↵
}↵
}↵
int main() {↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cin >> n >> k;↵
g.resize(n);↵
for (int i = 0; i < n - 1; i++) {↵
int u, v;↵
long long w;↵
cin >> u >> v >> w;↵
u--; v--;↵
g[u].push_back({v, w});↵
g[v].push_back({u, w});↵
}↵
s.assign(n, 0);↵
r.assign(n, false);↵
dc(0);↵
cout << a;↵
}↵
~~~↵
</spoiler>↵
↵
Спасибо за участие!!! Мы приносим прощения если что-то было не так, хотелось отметить что проверку на ИИ делало ИИ, а затем человек, поэтому могут быть ошибки. Прямо сейчас мы открываем доступ к чужим посылкам, если вы заметили ИИ, то пожалуйста, сообщите об этом [user:Arbuzik342,2026-10-23] с добавлением причин почему вы так считаете. ↵
↵
P.S. Мои навыки английского не так хороши да и перевести столько я не смогу без потери точности, может ли кто-то помочь мне в этом?
