原帖

大概题意： 给一棵树，树上每个点有点权，每次可以将一条路径上所有点权减一，求所有点权置零的最小操作次数。

今天吃饭灵光一现，口胡一个做法。

原题是树为一条链时的特殊情况。

考虑最小化操作次数，其实就是将树划分为不相交几条链，使链的数量最小，就是网络流经典的最小路径覆盖问题。

那么每次重新建图，令所有点权更新为减去当前最小点权，答案加上最小点权与路径条数的乘机，跑到所有点权为 0 时程序终止

算法复杂度Dinic跑二分图是 $O(n \sqrt m)$ 的 这里 $m$ 与 $n$ 同级，所有点权最多有 $n$ 种，最多跑 $n$ 次最小路径覆盖，所以总时间复杂度 $O(n^2 \sqrt n)$。大概能跑 $n \leq 10^3$ 量级

欢迎 dalao 来暴虐本蒻。