Ваша основная идея правильная. Вы считаете пути, у которых:

• обе конечные вершины имеют нечётную степень;
• все внутренние вершины имеют чётную степень.

Ниже исправленная версия с минимальным сохранением вашей структуры. Рекурсивные DFS заменены на итеративные, потому что при n = 2⋅10^5 рекурсия может привести к переполнению стека.

cpp
#include <iostream>
#include <vector>
using namespace std;

int k = 0;
vector<int> st;
vector<vector<int>> gr;
vector<bool> used;

void dfs_nch(int v) {
    vector<int> q = {v};
    used[v] = true;

    while (!q.empty()) {
        v = q.back();
        q.pop_back();
        k++;

        for (auto u : gr[v]) {
            if (used[u] || st[u] % 2 == 0) continue;
            used[u] = true;
            q.push_back(u);
        }
    }
}

void dfs_ch(int v) {
    vector<int> q = {v};
    used[v] = true;

    while (!q.empty()) {
        v = q.back();
        q.pop_back();

        for (auto u : gr[v]) {
            if (st[u] % 2 == 1) {
                k++;
                continue;
            }

            if (used[u]) continue;

            used[u] = true;
            q.push_back(u);
        }
    }
}

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

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        used.assign(n + 1, false);
        st.assign(n + 1, 0);
        gr.assign(n + 1, {});

        for (int i = 1; i < n; ++i) {
            int v, u;
            cin >> v >> u;

            gr[v].push_back(u);
            gr[u].push_back(v);
            st[v]++;
            st[u]++;
        }

        long long ans = 0;

        for (int i = 1; i <= n; ++i) {
            if (st[i] % 2 == 0 || used[i]) continue;

            dfs_nch(i);
            ans += k - 1;
            k = 0;
        }

        for (int i = 1; i <= n; ++i) {
            if (st[i] % 2 == 1 || used[i]) continue;

            dfs_ch(i);
            ans += 1LL * k * (k - 1) / 2;
            k = 0;
        }

        cout << ans << '\n';
    }
}

Почему рассматриваются именно такие пути

Ключевой игровой факт:

Первый путь является выигрышным для Тома тогда и только тогда, когда его концы имеют нечётные степени, а все внутренние вершины имеют чётные степени.

Для конечной вершины пути используется одно инцидентное ребро. Поэтому после первого хода у неё остаётся:

$$\deg(v)-1$$

свободных рёбер. Это число должно быть чётным, следовательно, исходная степень конца должна быть нечётной.

Для внутренней вершины пути используются два ребра. Остаётся:

$$\deg(v)-2$$

свободных рёбер. Это число должно быть чётным, следовательно, степень внутренней вершины должна быть чётной.

Эта чётность позволяет Тому после первого хода применять ответную стратегию: свободные продолжения можно разбивать на пары. На каждый ход Джерри Том выбирает соответствующее парное продолжение. В итоге без хода остаётся Джерри.

Если хотя бы один конец имеет чётную степень либо внутренняя вершина имеет нечётную степень, такую парную стратегию получает уже Джерри.

Таким образом, нужно посчитать пути следующего вида:

$$\text{нечётная вершина} \rightarrow \text{несколько чётных вершин} \rightarrow \text{нечётная вершина}.$$

Количество внутренних чётных вершин может быть нулевым.

---

Что делает первый DFS

cpp
dfs_nch(i);
ans += k - 1;

Здесь рассматриваются компоненты, состоящие только из вершин нечётной степени.

Поскольку исходный граф — дерево, каждая такая компонента также является деревом.

Если в компоненте k вершин, внутри неё имеется ровно:

$$k-1$$

рёбер.

Каждое такое ребро само является допустимым путём длины 1:

text
нечётная — нечётная

У него нет внутренних вершин, поэтому условие на внутренние чётные вершины автоматически выполняется.

Именно поэтому добавляется:

cpp
ans += k - 1;

---

Что делает второй DFS

Второй DFS обходит компоненту, состоящую только из чётных вершин:

cpp
dfs_ch(i);

При встрече соседней нечётной вершины выполняется:

cpp
k++;

То есть k становится количеством нечётных вершин, соединённых с этой чётной компонентой.

Можно выбрать любые две такие нечётные вершины. Путь между ними будет выглядеть так:

text
нечётная — чётная — чётная — ... — чётная — нечётная

Все внутренние вершины принадлежат рассматриваемой компоненте и имеют чётные степени.

Количество способов выбрать два конца:

$$C_k^2=\frac{k(k-1)}2.$$

Поэтому нужно прибавлять:

cpp
ans += 1LL * k * (k - 1) / 2;

---

Главная логическая ошибка

У вас было:

cpp
ans = k * (k - 1) / 2;

Здесь вы полностью затирали всё, что уже было посчитано:

• результаты первого DFS;
• результаты предыдущих компонент чётных вершин.

Например, пусть первая чётная компонента дала 3 пути, а вторая дала 6. Правильный результат должен увеличиться на:

$$3+6=9.$$

Ваш код сначала делал:

cpp
ans = 3;

а потом:

cpp
ans = 6;

В результате оставался только ответ для последней компоненты.

Исправление:

cpp
ans += 1LL * k * (k - 1) / 2;

---

Переполнение int

Даже после замены = на += выражение:

cpp
k * (k - 1)

вычислялось бы как int, потому что обе переменные имеют тип int.

При k = 200000:

$$200000\cdot199999\approx4\cdot10^{10},$$

что значительно больше максимального значения int:

$$2^{31}-1\approx2.1\cdot10^9.$$

Переполнение происходит до присваивания в long long.

Поэтому нужен множитель 1LL:

cpp
1LL * k * (k - 1) / 2

Теперь всё выражение вычисляется как long long.

---

Проблема рекурсивного DFS

Ваши функции могли вызвать рекурсию глубиной до 200000.

Например, для дерева-цепочки:

text
1 — 2 — 3 — ... — 200000

глубина DFS может быть линейной. Стандартного стека программы для такого количества вызовов часто недостаточно, поэтому программа может завершиться с ошибкой выполнения.

Итеративный DFS через:

cpp
vector<int> q;

использует динамическую память и безопасно работает при заданных ограничениях.

---

Почему нечётная вершина не посчитается дважды около одной чётной компоненты

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

В дереве это невозможно.

Если нечётная вершина была бы соединена с двумя вершинами одной чётной компоненты, то внутри компоненты существовал бы путь между этими двумя вершинами. Вместе с двумя рёбрами к нечётной вершине получился бы цикл.

Но исходный граф является деревом, поэтому циклов в нём нет.

Следовательно, каждая пограничная нечётная вершина учитывается ровно один раз.

---

Итоговая сложность для одного теста:

$$O(n)$$

по времени и

$$O(n)$$

по памяти. С учётом ограничения на сумму n решение укладывается в заданные пределы.

Намёк

Посмотрите не на логику split/merge, а на максимальное количество вершин декартова дерева.

Изначально их n, но каждое событие второго типа создаёт ещё одну вершину. Сравните возможное значение n + k с размером массива:

cpp
const int MAXN = 100005;
Node t[MAXN];

Также обратите внимание на тип результата функции merge: она возвращает номер вершины, а не величину типа long long.

Исправленный код

Изменения минимальны:

cpp
#include <iostream>
#include <chrono>
#include <random>

using namespace std;
using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node {
    int key, prior;
    ll len, sum;
    int left, right;
};

const int MAXN = 200005;
Node t[MAXN];

int root = 0;
int node_cnt = 0;

int get_key(int v) {
    return v ? t[v].key : 0;
}

ll get_len(int v) {
    return v ? t[v].len : 0;
}

ll get_sum(int v) {
    return v ? t[v].sum : 0;
}

void upd(int v) {
    t[v].key = get_key(t[v].left) + get_key(t[v].right) + 1;
    t[v].sum = get_sum(t[v].left) + get_sum(t[v].right) + get_len(v) * get_len(v);
}

void split(int v, int key, int &l, int &r) {
    if (!v) {
        l = r = 0;
        return;
    }

    int l_sz = get_key(t[v].left);

    if (l_sz < key) {
        split(t[v].right, key - l_sz - 1, t[v].right, r);
        l = v;
    } else {
        split(t[v].left, key, l, t[v].left);
        r = v;
    }

    upd(v);
}

int merge(int l, int r) {
    if (!l || !r) {
        return l ? l : r;
    }

    if (t[l].prior > t[r].prior) {
        t[l].right = merge(t[l].right, r);
        upd(l);
        return l;
    } else {
        t[r].left = merge(l, t[r].left);
        upd(r);
        return r;
    }
}

void bank(int key) {
    int l, m1, m, m2, r;
    split(root, key - 2, l, m1);
    split(m1, 1, m1, m);
    split(m, 1, m, m2);
    split(m2, 1, m2, r);

    if (m1 && m2) {
        ll k1 = t[m].len / 2;
        ll k2 = (t[m].len + 1) / 2;

        t[m1].len += k1;
        t[m1].sum = t[m1].len * t[m1].len;

        t[m2].len += k2;
        t[m2].sum = t[m2].len * t[m2].len;
    } else if (m1) {
        t[m1].len += t[m].len;
        t[m1].sum = t[m1].len * t[m1].len;
    } else {
        t[m2].len += t[m].len;
        t[m2].sum = t[m2].len * t[m2].len;
    }

    root = merge(merge(l, merge(m1, m2)), r);
}

void del(int key) {
    int l, m, r;
    split(root, key - 1, l, m);
    split(m, 1, m, r);

    ll p1 = (t[m].len + 1) / 2;
    ll p2 = t[m].len / 2;

    int v = ++node_cnt;
    t[v].key = 1;
    t[v].prior = rng();
    t[v].len = p1;
    t[v].sum = p1 * p1;
    t[v].left = t[v].right = 0;

    t[m].len = p2;
    t[m].sum = p2 * p2;

    root = merge(l, merge(merge(m, v), r));
}

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

    int n, p;
    cin >> n >> p;

    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;

        int v = ++node_cnt;
        t[v].key = 1;
        t[v].prior = rng();
        t[v].len = a;
        t[v].sum = 1LL * a * a;
        t[v].left = t[v].right = 0;

        root = merge(root, v);
    }

    int k;
    cin >> k;

    cout << t[root].sum << '\n';

    while (k--) {
        int e, v;
        cin >> e >> v;

        if (e == 1) {
            bank(v);
        } else {
            del(v);
        }

        cout << t[root].sum << '\n';
    }
}

Основная ошибка: недостаточный размер массива

У вас было:

cpp
const int MAXN = 100005;
Node t[MAXN];

Изначально декартово дерево действительно содержит n вершин, по одной вершине на каждое предприятие.

Но при разделении предприятия выполняется:

cpp
int v = ++node_cnt;

То есть появляется новая вершина декартова дерева.

При этом старая вершина m не удаляется: она начинает представлять левое предприятие, а новая вершина v представляет правое предприятие.

Следовательно, после каждого события второго типа количество когда-либо созданных вершин увеличивается на один.

Максимально возможно:

$$n=100000,$$ $$k=100000,$$

и все k событий могут быть разделениями. Тогда будет создано:

$$n+k=200000$$

вершин.

Ваш массив рассчитан только примерно на 100000:

cpp
Node t[100005];

Когда node_cnt станет больше 100004, код начнёт записывать за пределы массива:

cpp
int v = ++node_cnt;
t[v].key = 1;

Это неопределённое поведение. Возможны разные последствия:

• runtime error;
• повреждение других глобальных переменных;
• случайный неправильный ответ;
• программа может некоторое время работать, а затем падать;
• ошибка может проявляться только на больших тестах.

Исправление:

cpp
const int MAXN = 200005;

Поскольку:

$$n+k\le 200000.$$

Индекс 0 используется как фиктивная пустая вершина, а реальные вершины имеют номера от 1 до 200000, поэтому размер 200005 достаточен.

---

Неправильный тип функции merge

У вас было:

cpp
ll merge(int l, int r)

Но функция возвращает не сумму, не длину и не другое большое число. Она возвращает индекс корня декартова дерева:

cpp
return l;
return r;

Индексы имеют тип int, потому что:

cpp
int root;
int left, right;

Поэтому правильная сигнатура:

cpp
int merge(int l, int r)

В вашем варианте это обычно не приводило к неправильному ответу, поскольку возвращаемый long long затем неявно преобразовывался обратно в int:

cpp
root = merge(...);
t[l].right = merge(...);

Но тип был логически неверным. Кроме того, он скрывает смысл функции: merge возвращает номер корня объединённого дерева.

Это не основная причина падения, но это нужно исправить.

---

Тип функции get_key

У вас было:

cpp
ll get_key(int v)

Однако key хранит размер поддерева:

cpp
int key;

Количество предприятий не превышает 200000, поэтому int более чем достаточен.

Исправлено на:

cpp
int get_key(int v)

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

---

Почему логика bank корректна

Разберём ваши четыре операции split.

Пусть банкротится предприятие с номером key.

cpp
split(root, key - 2, l, m1);

После этого:

• l содержит первые key - 2 предприятий;
• m1 содержит всё остальное, начиная с предприятия key - 1.

Далее:

cpp
split(m1, 1, m1, m);

Теперь:

• m1 — предприятие с номером key - 1, то есть левый сосед;
• m — всё начиная с банкротящегося предприятия.

Далее:

cpp
split(m, 1, m, m2);

Теперь:

• m — банкротящееся предприятие;
• m2 — всё справа от него.

И наконец:

cpp
split(m2, 1, m2, r);

Теперь:

• m2 — правый сосед;
• r — все предприятия после правого соседа.

Получается структура:

text
l | m1 | m | m2 | r

где:

• m1 может отсутствовать, если банкротится первое предприятие;
• m2 может отсутствовать, если банкротится последнее предприятие;
• m всегда существует.

Это разбиение корректно.

---

Почему части банкротящегося предприятия распределены правильно

Если имеются оба соседа, вы делаете:

cpp
ll k1 = t[m].len / 2;
ll k2 = (t[m].len + 1) / 2;

Для чётной длины, например 8:

text
k1 = 4
k2 = 4

Для нечётной длины, например 7:

text
k1 = 3
k2 = 4

По условию часть, расположенная ближе к истоку, должна быть меньше.

Предприятия идут от истока слева направо, поэтому:

• левому соседу нужно передать меньшую часть;
• правому соседу — большую.

Ваш код делает именно это:

cpp
t[m1].len += k1;
t[m2].len += k2;

То есть здесь ошибки нет.

---

Почему достаточно вручную менять sum у m1 и m2

После последовательности split деревья m1 и m2 содержат ровно по одной вершине.

Например:

cpp
split(m1, 1, m1, m);

Левая часть после этого содержит ровно один элемент. Поэтому у корня m1 нет других элементов поддерева.

Его сумма равна просто квадрату его длины:

cpp
t[m1].sum = t[m1].len * t[m1].len;

Аналогично для m2.

После последующих вызовов merge функция upd пересчитает суммы всех предков:

cpp
root = merge(merge(l, merge(m1, m2)), r);

Так что эта часть реализована правильно.

---

Почему предприятие m можно просто не добавлять обратно

При банкротстве предприятие исчезает.

После распределения его участка вы собираете дерево без m:

cpp
root = merge(merge(l, merge(m1, m2)), r);

Это правильно.

Память вершины m не переиспользуется, но это допустимо. Именно поэтому нужно хранить до n+k вершин, а не только текущее количество предприятий.

Количество активных предприятий может уменьшаться, но node_cnt никогда не уменьшается.

Например:

1. Создано 100000 начальных вершин.
2. Выполнено 50000 разделений — создано ещё 50000.
3. Выполнено много банкротств — активных предприятий стало мало.
4. Затем снова происходят разделения — создаются новые вершины с новыми индексами.

Удалённые узлы остаются в массиве как неиспользуемые, поэтому размер массива определяется общим числом созданий, а не максимальным текущим количеством предприятий.

---

Почему логика разделения корректна

При событии второго типа:

cpp
split(root, key - 1, l, m);
split(m, 1, m, r);

получается:

text
l | m | r

где m — разделяемое предприятие.

Вы вычисляете:

cpp
ll p1 = (t[m].len + 1) / 2;
ll p2 = t[m].len / 2;

Для нечётной длины, например 7:

text
p1 = 4
p2 = 3

После этого:

cpp
t[m].len = p2;
t[v].len = p1;

И собираете:

cpp
merge(m, v)

То есть старый узел m находится левее нового узла v.

Следовательно:

• ближе к истоку находится m, его длина p2 = 3;
• дальше от истока находится v, его длина p1 = 4.

Это полностью соответствует условию: меньшая часть должна находиться ближе к истоку.

Названия p1 и p2 немного сбивают с толку, но сама логика правильная.

---

Зачем добавлено 1LL * a * a

В начальном заполнении у вас было:

cpp
t[v].sum = a * a;

Согласно ограничениям:

$$a_i\le 10^4,$$

поэтому:

$$a_i^2\le 10^8,$$

и конкретно здесь переполнения int не произойдёт.

То есть исходная строка была безопасна.

Тем не менее я заменил её на:

cpp
t[v].sum = 1LL * a * a;

Это подчёркивает, что квадрат вычисляется в long long, и защищает код при возможном изменении ограничений.

После объединений длина участка может быть намного больше 10^4, поэтому в остальных местах вы правильно используете ll len.

Максимальная суммарная длина реки:

$$100000\cdot10000=10^9.$$

Квадрат такой длины:

$$10^{18},$$

что уже требует long long, но ещё помещается в него.

---

Почему вся сумма помещается в long long

Пусть длины предприятий равны:

$$x_1,x_2,\ldots,x_m.$$

Суммарная длина реки постоянна:

$$x_1+x_2+\ldots+x_m\le10^9.$$

Сумма квадратов максимальна, когда практически вся длина сосредоточена у одного предприятия:

$$x_1^2+x_2^2+\ldots+x_m^2 \le (x_1+x_2+\ldots+x_m)^2 \le 10^{18}.$$

long long хранит значения примерно до:

$$9.22\cdot10^{18}.$$

Следовательно, тип ll достаточен.

---

Сложность

Операции неявного декартова дерева:

• split;
• merge;
• поиск предприятия по позиции через split

работают в среднем за:

$$O(\log n).$$

Каждое событие выполняет константное количество таких операций, поэтому общая ожидаемая сложность:

$$O((n+k)\log(n+k)).$$

Память:

$$O(n+k).$$

При ограничениях n, k ≤ 100000 это должно укладываться в лимиты.

Главная причина проблем вашего кода — запись за границы массива t при большом количестве разделений.