Я застрял с этой проблемой, может ли кто-нибудь сказать мне, какой алгоритм я могу использовать?
В городе , улицах сделаны таким образом, что из любого дома вы можете добраться до другого, не повторяя улиц, через которые вы проходите, и только проходя через каждую улицу. Но так как город системы строительства является новым, был зафиксирован высокий показатель вандализма. Ваша задача - помочь построить сигнальную систему , чтобы на каждой улице был сигнал с опасностью прохода через эту улицу. Опасность улицы определяется как количество маршрутов, по которым вы обязательно должны пройти через эту улицу.
ВХОД: целое число N (2 <= N <= 10 ^ 6), которое представляет количество домовследующие N-1 строки содержат два целых числа A, B (A, B <= N),, которые представляют улицу между домом A и домом B.
Это проблема дерева m-ary, так как края n-1 Это как найти все возможныеподдерево и подсчитать, сколько раз путь проходит через край, но меня немного смущает вопрос, буду ли я использовать взвешенное дерево или есть простой способ сделать это.