题解 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就当顺便练练复杂度分析了。

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