n вершин с номерами от 0 до n - 1. Его рёбра заданы массивом links длины n - 1: пара [a, b] означает ребро между вершинами a и b. Какая вершина корень — неизвестно.
О дереве сделаны утверждения claims: пара [u, v] значит «u — родитель v», причём u и v всегда соединены ребром. Известно лишь, что верны хотя бы need из этих утверждений.
Верните количество вершин, которые могут быть корнем: если подвесить дерево за такую вершину, верными окажутся не меньше need утверждений.links=[[0, 1], [1, 2], [1, 3]], claims=[[1, 0], [1, 2], [3, 1]], need=2 → 2
Корень 0: верно только «1 — родитель 2». Корень 1: верны «1 — родитель 0» и «1 — родитель 2». Корень 2: верно только «1 — родитель 0». Корень 3: верны все три. Подходят корни 1 и 3.
links=[[0, 1]], claims=[[0, 1]], need=0 → 2
При need = 0 условие выполняется для любого корня — ответ 2.
links=[[2, 0], [0, 1]], claims=[[0, 1], [1, 0]], need=2 → 0
Утверждения «0 — родитель 1» и «1 — родитель 0» не могут быть верны одновременно, так что подходящих корней нет.
[u, v] — ребро дерева, утверждения не повторяютсяlinks=[[0, 1], [1, 2], [1, 3]], claims=[[1, 0], [1, 2], [3, 1]], need=2
2
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 63 теста на сервере, включая скрытые.