P5521 [yLOI2019] 梅深不见冬 题解

· · 题解

Step1 脑补fusu的行走过程，建立模型：

记对于 i 节点的答案为 d_i，思考 d_i 的意义为行走的“任意时刻”场面上梅花数量的最大值。

我们希望建立从叶子节点向根递推的关系。由此，不妨先考虑简单一些的初始情况：

当节点为叶子节点时，d_i=w_i。

当节点的孩子全都是叶子节点时:

我们记 S_i 为节点 i 的孩子集合，则：

------------ 那么，上述式子是否对于所有节点都成立？思考反例，答案是否定的。 事实上，在fusu行走的过程中，我们在孩子 $j$ 的子树中放置 $d_j$ 朵梅花时： 场面中的梅花数量= $d_j$ $+$ 在之前走过的孩子节点中放置的梅花数量 综上，我们有如下的递推关系： $d_i=\max\{max_{j\in S_r}(d_j+\sum_{early(k,j)}w_k),w_i+\sum_{j\in S_i}w_j\}

其中拜访节点的序列是任意的，我们可以自己决定。

Step2 确定正确序列服从的贪心关系

所有孩子节点具有的数值为 d_j,w_j，它们的任意性很强，唯一具有的特点为 d_j\geq w_j。

把上面那个玩意揪出来，我们希望最小化的是：

max_{j\in S_r}(d_j+\sum_{early(k,j)}w_k)

不妨先取例测试，这里我取的是：

i) \{(d_j,w_j)\}=(1,1),(2,2),(3,3),(4,4)

调整这些数对的顺序，我们发现无论怎样调整，答案都是 1+2+3+4=10。

ii) \{(d_j,w_j)\}=(1,0),(2,1),(3,2),(4,3.5)

严格意义上，这里取 0,3.5 是不规范的，但可以将 0 视作一个无穷小量，并同时将它们放大。

注意到最优的序列之一为：

(1,0),(3,2),(2,1),(4,3.5)

运气很好，介于此及 d 和 w 的大小关系，可以猜想最优序列按照 d-w 的数值随拜访次序递减。

Step3 复杂度分析+优化

遍历一遍树的复杂度： O(n)

孩子节点排序的总复杂度： O(nlogn)，因为每个孩子节点都仅考虑一遍。

足以通过本题。

Step4 Coding

以下是主要代码：


bool cmp(node2 x,node2 y){
    return (x.d-x.w)>(y.d-y.w);
}

void dfs(int u){
    int cnt2=0;
    for(int j=head[u];j!=0;j=edge[j].nxt){
        int v=edge[j].v;
        dfs(v);
        d[u]+=w[v];
    }
    d[u]+=w[u];
    for(int j=head[u];j!=0;j=edge[j].nxt){
        int v=edge[j].v;
        c[cnt2].w=w[v];
        c[cnt2].d=d[v];
        cnt2++;
    }
    if(cnt2==0){
        return;
    }
    sort(c,c+cnt2,cmp);
    int sumw=0;
    for(int i=0;i<cnt2;i++){
        d[u]=max(d[u],sumw+c[i].d);
        sumw+=c[i].w;
    }
}