Чтобы решить эту задачу, давай сначала разберёмся, что такое цепь в графе. Цепь — это последовательность вершин, в которой каждая последующая вершина соединена ребром с предыдущей. Длина цепи определяется количеством её рёбер.
Нам нужно посчитать, сколько есть цепей длиной четыре, соединяющих начальную вершину S с какой-либо концевой вершиной.
На изображении мы видим дерево, то есть связный граф без циклов. Давай последовательно проследим все пути от вершины S длиной четыре:
- Из S мы можем пойти влево или направо, рассмотрим сначала левую часть.
- Идя налево, следующей вершиной будет только одна вершина.
- Оттуда возможны два пути: к вершине слева или справа.
- Обе эти вершины имеют по две ветви, ведущие к концевым вершинам.
Следовательно, с левой стороны получается 4 цепи длиной четыре (2 пути от второй вершины, умноженные на 2 завершающих ветви каждой из них).
Теперь рассмотрим правую часть:
- С вершины S в правую сторону мы можем пойти двумя путями.
- Один путь ведёт на вершину с тремя ветвями, по которым можно пойти к концевым вершинам, образуя три цепи длиной четыре.
- Другой путь ведёт к вершине с двумя ветвями, причём одна из них ведёт к концевой вершине напрямую, что даёт ещё одну цепь, а другая сначала ведёт к вершине с двумя концевыми ветвями, добавляя ещё две цепи.
Итак, с правой стороны у нас получается 3 + 1 + 2 = 6 цепей длиной четыре.
Суммируем цепи с обеих сторон, и получаем 4 + 6 = 10 цепей длиной четыре.
Правильный ответ — 10.
