笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

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