CF1637F Sol

· · 题解

很神秘的题。

首先很明显所有的塔都建在叶子（含度数为 1 的根）上面最优。为了单独照顾那些太高的点而在其它地方建显然不如全部交给叶子打包处理。

那么这里有一个转化：一个点被覆盖当且仅当它作根时，它有至少两个儿子的子树内建了高度不小于 h_i 的塔，或者它自己头上建了一个。

其实这里对路径问题的处理有点像点分治，就是只考虑路径两端分别在两棵子树里的情况。

两棵子树的话有点复杂，要不转成一棵子树？

所以先把 h_i 最大的点拎出来当根，这样它两边都得有一棵子树符合条件。那么这时如果再往下搜索，相当于只用使除根以外的每个点儿子的一棵子树高度达到 h_i 即可，因为根的另一侧肯定有另一个达到 h_i 的。

那么就是维护每个点下面叶子上面建的塔的最大高度，如果一个点的儿子遍历完了发现下面一座高度足够的塔都没有，就把那个最高的塔往上加到 h_i，否则直接用那个最高的塔。到根节点的时候要取最高和次高的塔计算。

这样加出来就是答案了。

ll n,h[N],pos,ans;
vector<ll> e[N];
ll dfs(ll p,ll f) {
    ll mx1=0,mx2=0;
    for (ll i:e[p]) if (i!=f) {
        mx2=max(mx2,dfs(i,p));
        if (mx1<mx2) swap(mx1,mx2);
    }
    if (p==pos) ans+=max(h[p]-mx1,0ll)+max(h[p]-mx2,0ll);
    else ans+=max(h[p]-mx1,0ll),mx1=max(mx1,h[p]);
    return mx1;
}
int main() {
    scanf("%lld",&n);
    for (ll i=1;i<=n;i++) {
        scanf("%lld",&h[i]);
        if (h[i]>h[pos]) pos=i;
    }
    for (ll i=1,x,y;i<n;i++) scanf("%lld%lld",&x,&y),e[x].pb(y),e[y].pb(x);
    dfs(pos,0);
    printf("%lld",ans);
    return 0;
}