因为很晚了所以不规范使用 Latex 来书写了，见谅。

假设将点 1 删掉，原图变成若干森林，下简称“区块”为森林中的一个树。

假设我们钦定若干军队不在本区块驻守，那么可以通过 O(sz) 的时间复杂度来得知一个区块的最早封锁时间。（树上 dp ，dp i = min (max(每棵子树的封锁时间),一个子树内军队走到 i 的最短时间)）

考虑外层套二分答案，设 T 为二分的 mid ，我们可以先初步假设每一个可以在 T 时间内跑到本区块的根的军队全部外派到其他区块，那么可以将所有 dep < T 的军队先暂时删掉。对每个区块进行树上 dp ，发现所有最早封锁时间 > T 的区块需要由其他区块的军队支援。如果一个区块在外派后封锁时间超额，将本区块最晚到达根节点的军队留在本土封锁。

由此我们可以得到若干外派军队抵达首都的时间，与若干需要被支援的区块。贪心的把 更早到首都的军队 匹配向 由首都走向该区块的边更长 的区块，判断两时间相加是否均 <= T 且 外派军队数 >= 需要支援的区块个数 即可完成一次二分的判定。

此时 WA on test 7 & 10 ，发现外派后本土军队自动驻守并非最优解，大胆猜想如果本土最远（距离首都最远，即外派抵达时间最长）的军队 加 本区块到首都的距离小于等于 T 即可“假装”外派军队。因为 在后续匹配过程中可以将本过程视为本土军队走到首都再走回来，因此做法不劣，并且能考虑到交换军队封锁的情况。

不太确定做法是否完全正确，欢迎来 hack 我。

code: https://www.luogu.com.cn/record/191753039