题解

思路推导

把树根定为 $1$。路径可以重复覆盖，因此可以把一个被选工人的实际负责段在原路径内向下缩短，使最终负责段互不穿越；这不会增加费用。令 $dp_u$ 表示覆盖 $u$ 子树内全部道路以及边 $(u,\operatorname{parent}_u)$ 的最小费用。

若负责覆盖父边的工人从 $u$ 子树中的节点出发，并到达 $u$ 的严格祖先，那么这名工人沿途经过的子树根边已经由它覆盖；其他儿子子树仍需分别支付对应的 $dp$。因此每名工人都可以维护一个“若它最终负责当前父边时的总代价”候选值。

做法

先求 Euler 序，使每棵子树和其中出发的工人都对应连续区间。线段树的每个叶子对应一名工人，维护候选值，支持区间加、单点赋值与区间最小值。

后序处理节点 $u$。设儿子答案之和为 $S$：

• 对每个儿子 $v$，把 $v$ 子树内所有工人候选值增加 $S-dp_v$，表示其路径负责穿过 $v$ 时，其他儿子仍需独立覆盖；
• 对从 $u$ 出发的工人 $i$，把候选值设为 $S+c_i$；
• 对终点恰为 $u$ 的工人，将候选值删除，因为它不覆盖 $u$ 的父边；
• $dp_u$ 是 $u$ 子树工人区间的最小候选值。

根没有父边，答案就是根的所有儿子答案之和。任何儿子无解时，全局也无解。

正确性证明

按子树后序归纳。处理 $u$ 前，每名仍在线段树中的工人候选值，恰为它负责覆盖当前尚需向上的连续路径时，已经确定的各支线子树最小费用与自身费用之和。

合并儿子时，候选工人若来自儿子 $v$，其路径代替 $dp_v$ 覆盖了经过的主链，而其他儿子必须独立支付，故增加 $S-dp_v$ 恰好。由 $u$ 出发的工人尚未覆盖任何儿子主链，所以候选值为 $S+c_i$。终点为 $u$ 的工人不覆盖父边，删除它们后，剩余候选恰好枚举了覆盖父边的所有合法最后选择。取最小值得到 $dp_u$。

归纳至根，各根儿子子树互不可能由同一工人跨越，答案必须且只需相加，因此算法正确。

部分分算法

当 $n,m\le18$ 时，可枚举工人子集，直接检查其路径并集是否覆盖全部道路。

当树是一条链时，每名工人对应深度区间。令 $f_r$ 为覆盖深度前缀到 $r$ 的最小费用；对右端点为 $r$、左端点为 $l$ 的区间，用 $\min_{k\in[l-1,r-1]}f_k+c$ 转移，配合区间最小值结构即可。

复杂度分析

每名工人只被插入和删除一次，每条树边对应一次区间加。时间复杂度为 $O((n+m)\log m)$，空间复杂度为 $O(n+m)$。