luogu1084 疫情控制

$\texttt{loj}$上也有(2607),数据稍微强一点,需要卡一下常(可能是我自带大常数)。

题意

$N$个城市组成一棵树,$1$号节点是首都,也是根节点。$M$个军队驻扎在某些城市上,军队可移动,从一个点移动到邻接点花费的时间为边权;也可以原地驻扎,但是不能驻扎在首都。求最少的时间,可以将调度军队使得从每个叶子节点到根节点的路径上都有驻军。

$2≤m≤n≤50,000$
继续阅读