Задача D. Дерево невидимого Жанадиля

Дано связное дерево с $N$ вершин. Невидимый Жанадиль выбирает какое-то подмножество вершин из заданного дерева, и удаляет все выбранные вершины и связанные с ними ребра из дерева. В результате получится лес из $X$ связанных компонент, где компонента $i$ содержит $sz_i$ вершин, для $1 <= i <= X$. Основываясь на этом, Жанадиль считает значение $$F = \sum_{i=1}^{X} 2^{sz[i]}$$. Ваша задача состоит в том чтоб посчитать и вывести сумму значений $F$ по всем возможным подмножествам. Выведите ответ по модулю $10^9 + 7$. Первая строка содержит целое число $N$ $(1 <= N <= 2 * 10^5)$ — количество вершин в дереве. Каждая из следующих $N - 1$ строк содержит два целых числа $u_i$ и $v_i$ ($1 <= u_i <= N$, $1 <= v_i <= N$ и $u_i \neq v_i$) — ребро дерева между вершинами $u_i$ и $v_i$. Выведите сумму значений $F$ по всем возможным подмножествам по модулю $10^9 + 7$. Данная задача содержит пять подзадач, в каждой подзадаче выполняются дополнительные ограничения:

1. $1 <= N <= 20$. Оценивается в 8 баллов.
2. $1 <= N <= 200$. Оценивается в 13 баллов.
3. $1 <= N <= 2000$. Оценивается в 18 баллов.
4. $1 <= N <= 2 * 10^5$, у каждой вершины не более двух соседей. Оценивается в 14 баллов.
5. Ограничения из условия. Оценивается в 47 баллов.

Вход

3
1 2
2 3

Ответ

26

Вход

5
1 2
1 3
5 1
5 4

Ответ

216

В первом примере из условия сушествует $8$ различных возможных подмножеств, $F$ приобретает значения: $0$, $2$, $2$, $2$, $4$, $4$, $4$, $8$. Сумма этих значений равна $0 + 2 * 3 + 4 * 3 + 8 = 26$.

Задача E. НурлашКО

АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа $G$, состоящий из $n$ вершин, без ребер, во время игры игроки выполняют $q$ операций. Операции бывают следующих типов:

1. Добавить ориентированное ребро из вершины $u_i$ в вершину $v_i$.
2. Вывести $x_i$, если существует ориентированный путь из вершины 1 в вершину $x_i$, иначе $0$.

Гарантируется, после операции граф останется ациклическим. Ациклический граф - случай ориентированного графа, в котором отсутствуют ориентированные циклы. Первая строка входных данных содержит три целых числа $n$, $q$ и $t$ $(1 <= n, q <= 10^6, 0 <= t <= 1)$ — количество вершин, количество операций и константное число. Каждая из следующих $q$ строк содержит описание одного запроса.

1. Запросы первого типа заданы в формате: $1$ $a_i$ $b_i$ $(0 <= a_i, b_i <= 2\cdot10^9)$.
2. Запросы второго типа заданы в формате: $2$ $a_i$ $(0 <= a_i <= 2\cdot10^9)$.

Обратите внимание, что вершины $u_i$, $v_i$ для запросов типа $1$ и вершина $x_i$ для запросов типа $2$ закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: {
$u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1$

$x_i = (a_i \oplus (t*lastans)) \mod n + 1$

} где $lastans$ — последний ответ на запрос типа $2$ (изначально $lastans$ равен $0$). Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как $xor$. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$. Гарантируется, что во входных данных присутствует хотя бы один запрос типа $2$. Для каждого запроса второго типа выведите ответ в отдельной строке. Данная задача содержит 5 подзадач, в каждой подзадаче выполняются ограничения из условий:

1. Тесты из условий. Оценивается в $0$ баллов.
2. $n, q <= 10^3$, $u_i = 1$, $t = 0$. Оценивается в $11$ баллов.
3. $n, q <= 10^3$. Оценивается в $18$ баллов.
4. $t = 0$. Оценивается в $39$ баллов.
5. Ограничения из условия. Оценивается в $32$ баллов.

Вход

5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3

Ответ

1
0
2
0
4

Вход

5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3

Ответ

1
0
2
0
4

Задача F. Сделайте неотрицательным!

Тима считает массив целых чисел хорошим если все числа в массиве неотрицательные. У Тимы есть массив $a$ состоящий из $n$ целых чисел. Тима хочет сделать его хорошим, для этого он может делать следующую операцию:

• выбрать три целых числа $i,j, x$ такие, что $1 <= i,j <= n, i \ne j, 1 <= x <= 10^9$ и $a_i \ge x$, а затем из числа $a_i$ отнять $x$, а к числу $a_j$ прибавить $x$. Стоимость такой операции $|i - j| \cdot x$ тенге.

Помогите Тиме, потратив минимальное количество тенге сделать массив хорошим. В первой строке находятся два целых числа $n, type (1 <= n <= 3 \cdot 10^5, 0 <= type <= 1)$. Во второй строке находятся $n$ целых числа $a_1,a_2, ..., a_n(-10^8 <= a_i <= 10^8)$. Гарантируется, что можно сделать массив $a$ хорошим. В первой строке выведите минимальное количество тенге, которое необходимо чтобы сделать массив хорошим. Если $type = 1$, во второй строке выведите одно целое число $k (0 <= k <= 2 \cdot n)$ — количество операции. В следующих $k$ строках выведите по три целых числа $i,j,x(1 <= i,j <= n, i \ne j, 1 <= x <= 10^9)$ — описания операций. Вам не надо минимизировать количество операций, но нужно минимизировать количество потраченных тенге. Если $type = 0$, то кроме минимального количество тенге, ничего выводить не надо. Задача состоит из восьми подзадач:

1. Примеры из условия. Оценивается в 0 баллов.
2. $n <= 10, type = 0, -1 <= a_i <= 1$. Оценивается в 8 баллов.
3. $n <= 200, type = 0, -10 <= a_i <= 10, |a_1| + |a_2| + ... + |a_n| <= 400$. Оценивается в 16 баллов.
4. $n <= 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 0$. Оценивается в 12 баллов.
5. $n <= 2000, type = 0, -1 <= a_i <= 1$. Оценивается в 15 баллов.
6. $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8, a_1 + a_2 + ... + a_n = 1$. Оценивается в 13 баллов.
7. $n <= 3 \cdot 10^5, type = 0, -10^8 <= a_i <= 10^8$. Оценивается в 15 баллов.
8. $n <= 3 \cdot 10^5, type = 1, -10^8 <= a_i <= 10^8$. Оценивается в 21 баллов.

Вход

7 0
1 1 -1 0 -1 1 1

Ответ

2

Вход

4 1
4 -2 -2 1

Ответ

5
3
1 2 2
1 3 1
4 3 1