_皎月半洒花 的博客

_皎月半洒花 的博客

反抗命运的镇魂曲停歇之前,你绝对不可以说我懦弱,绝对不可以说我没有殊死一搏。

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

posted on 2019-11-06 14:54:36 | under 题解 |

唔嗯,只是提供一个新的思路。

随机跳题跳到了这题,觉得有点意思就花了 $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就当顺便练练复杂度分析了。

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 ;
}