Олимпиадный тренинг

Задача . H. Обрезание дерева


Задача

Темы: дп поиск в глубину и подобное битмаски *3200

Вам дано дерево с \(n\) вершинами.

Герой \(k\) раз делает следующую операцию:

  • Выбрать некоторое ребро.
  • Удалить его.
  • Выбрать одну из двух оставшихся частей и удалить ее.
  • Записать количество вершин в оставшейся части.

Вам дано изначальное дерево и последовательность выписанных чисел. Найдите количество способов сделать операции так, что выписанные числа совпадут с данными числами. Поскольку ответ может быть очень большим, найдите его по модулю \(998\,244\,353\). Два способа считаются различными, если в какой-то операции выбранное ребро или остающаяся часть различаются.

Входные данные

В первой строке находится единственное целое число \(n\) (\(2 \leq n \leq 5000\)) — количество вершин.

Каждая из следующих \(n-1\) строк содержит два целых числа \(s\), \(f\) (\(1 \leq s, f \leq n\), \(s \neq f\)) — описание ребра \((s, f)\).

Следующая строка содержит единственное целое число \(k\) (\(1 \leq k \leq \min{(6, n - 1)}\)) — количество операций.

В следующей строке находится \(k\) целых чисел \(s_1, s_2, \ldots, s_k\) (\(n > s_1 > s_2 > \ldots > s_k \geq 1\)) — выписанные числа.

Выходные данные

Выведите единственное целое число — ответы на задачу по модулю \(998\,244\,353\).

Примечание

В первом тесте есть четыре возможных способа сделать операции:

  • Удалить ребро \((1, 2)\) и удалить вершину \(1\). Удалить ребро \((2, 3)\) и удалить вершину \(2\).
  • Удалить ребро \((1, 2)\) и удалить вершину \(1\). Удалить ребро \((3, 2)\) и удалить вершину \(3\).
  • Удалить ребро \((3, 2)\) и удалить вершину \(3\). Удалить ребро \((1, 2)\) и удалить вершину \(1\).
  • Удалить ребро \((3, 2)\) и удалить вершину \(3\). Удалить ребро \((2, 1)\) и удалить вершину \(2\).

Во втором тесте есть два возможных способа сделать операции:

  • Удалить ребро \((4, 1)\) и удалить часть с вершиной \(4\). Удалить ребро \((2, 3)\) и удалить часть с вершиной \(2\).
  • Удалить ребро \((4, 1)\) и удалить часть с вершиной \(4\). Удалить ребро \((3, 2)\) и удалить часть с вершиной \(3\).

Примеры
№Входные данныеВыходные данные
1 
3
1 2
2 3
2
2 1
 
4
2 
7
2 1
3 2
4 1
5 3
6 4
7 4
2
4 2
 
2
3 
7
1 2
1 3
1 4
2 5
3 6
4 7
1
2
 
3
4 
7
1 2
1 3
1 4
2 5
3 6
4 7
4
6 5 2 1
 
24
5 
8
1 2
2 3
3 4
3 5
3 6
3 7
3 8
2
7 4
 
0

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++3
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет