这是一个树形 DPDPDP 和 LCALCALCA （最近公共祖先）的问题。下面是解题思路的详细解释：
建图： 根据输入的城市和道路信息，建立一颗以城市 111 为根的树状图。
DFSDFSDFS 计算 dpdpdp 数组： 使用深度优先搜索（ DFSDFSDFS ）计算每个城市在驻扎军队和不驻扎军队两种情况下的花费。这样得到了 dpdpdp 数组，其中 dpdpdp [ 000 ][ iii ]表示在城市 iii 不驻扎军队时的花费， dpdpdp [ 111 ][ iii ]表示在城市 iii 驻扎军队时的花费。
计算 LCALCALCA ： 利用 LCALCALCA 算法计算两个城市之间的最小开销。 LCALCALCA 算法的目标是计算两个城市的最近公共祖先，以及在不同条件下的最小开销。
处理每个国王的要求： 遍历每个国王的要求，使用 LCALCALCA 算法计算在给定的条件下的最小开销。如果无法满足要求，则输出 −1-1−1 。
整体而言，这个算法的时间复杂度为 OOO ( nlognnlognnlogn )，其中 nnn 为城市数量。
