题解 P3931 【SAC E#1 - 一道难题 Tree】

唔嗯，只是提供一个新的思路。 随机跳题跳到了这题，觉得有点意思就花了$3min$给$A$掉了，并且似乎是个没人写过的思路……？ 题目意思就是让从根到每个叶子的路径上有至少一条边被割。那么不妨设计一个zz状态$f_i$，$f_i$表示前$i$个叶子被割完的最小代价。转移的时候考虑借助$dfs$序。如果$dfn_x=dfn_{fa_x}+sz_{fa_x}-1$，那么就说明是本子树内$dfs$序最靠后的一个节点，那么就有转移 $$f_i=f_{i-ctn_{fa_x}}+cost_{fa_x}$$ 其中$cost_x$表示与$fa_x$间连边的$val$，$ctn_x$表示$x$子树内有多少叶子。 也就是说我们可以通过删掉$fa$来搞掉这整棵子树。同理我们可以不断找深度更小的祖先，方法也大体类似。 下面说一下聚合分析出来的复杂度。不妨令$end_x$表示以$x$为根的子树内$dfn$序最大的点，如果$end_x=end_{fa_x}$那么我们令$end_x=x$，同时令$ofa(end_x)=x$。 那么对于每个$x$都有唯一的$end_x$，也只会在遍历到$end_x$的时候会向上回溯到$x$，那么总的复杂度就是$O(n+\sum({dep_x-dep_{end_x}}))$。考虑后一部分的复杂度，在同一棵大子树内，最劣的情况显然是对于每个叶子都要向上跳，这样的情况只会发生在下一个叶子的$ofa$恰是上一个叶子的$ofa$的$fa$。也就是第一个跳$1$，第二个跳$2$……注意这样最多跳$\sqrt n$次，所以第二部分的复杂度就是$1+2+3\cdots+\sqrt n=O(n)$（类似卡长链剖分的那种树）。 于是最后的复杂度为$O(n)+O(n)$. 233就当顺便练练复杂度分析了。 ```cpp void dfs(int u, int fr){ bool fg = 1 ; dfn[u] = ++ Id, sz[u] = 1, fa[u] = fr ; for (int k = head[u] ; k ; k = next(k)){ if (to(k) == fr) continue ; fg = 0, cost[to(k)] = val(k) ; dfs(to(k), u), sz[u] += sz[to(k)], ctn[u] += ctn[to(k)] ; } if (fg) Ls[++ tot] = u, ctn[u] = 1 ; } int main(){ cin >> N >> rt ; int i, j, u, v ; for (i = 1 ; i < N ; ++ i) u = qr(), v = qr(), j = qr(), add(u, v, j) ; dfs(rt, 0) ; for (i = 1 ; i <= tot ; ++ i){ int n = Ls[i], nid = dfn[n] ; f[i] = f[i - 1] + cost[Ls[i]] ; while (fa[n]){ if (fa[n] != rt && nid == dfn[fa[n]] + sz[fa[n]] - 1) f[i] = min(f[i], f[i - ctn[fa[n]]] + cost[fa[n]]) ; else break ; n = fa[n] ; } } cout << f[tot] << endl ; return 0 ; } ```