Заснеженные дороги

Во-первых, заметим, что существует такое $$$C$$$, что для любого уровня снега меньше $$$C$$$ граф остается связным, а для любого уровня снега не меньше $$$C$$$ - становится несвязным. Это значение $$$C$$$ можно найти, например, с помощью бинарного поиска по уровню снега и проверкой на связность любым алгоритмом обхода графа.

Во-вторых, при увеличении уровня снега количество опасных городов не уменьшается. Значит, для решения задачи достаточно сделать бинарный поиск по уровню снега, а затем найти количество опасных городов. По определению город является опасным тогда и только тогда, когда он является точкой сочленения в графе. Воспользуемся известным алгоритмом поиска точек сочленений в графе https://e-maxx.ru/algo/cutpoints и получим решение для все задачи с временной сложностью $$$\mathcal{O}((n + m)logC)$$$.