[COCI2020-2021#2] Sjekira 题解

· · 题解

根据题目我们可以发现最优解为：先将权值大的的顶点优先与和它连接的点删除。 所以我们就得到了一个时间复杂度 O(n) 的公式：

\sum_{i=1}^{n}T-\max(T_i)+\sum_{i=1}^{n-1}\max(T_x,T_y)

证明：因为每一个点至少要和其它数合并一次，所以 \operatorname{ans} 需要加上 \sum_{i=1}^{n}T。并且最大的那个数只会被计算到一次（因为最开始就把它给删了），所以 \operatorname{ans} 还需要减去 \max(T_i)。然后，权值大的那个数需要在它于小顶点删除的时候又要重新使用（因为题目说：断开一条边的代价为该边连接的两个连通块中各取一个最大权值的顶点之和），所以 \operatorname{ans} 还要加上 \sum_{i=1}^{n-1}\max(T_x,T_y)。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum,maxa,a[1000005]/*权值*/;
signed main()
{
    cin>>n;//输入
    for(register int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];//总和
        maxa=max(a[i],maxa);//最大值
    }
    sum-=maxa;//利用公式
    for(register int i=1;i<=n-1;i++)
    {
        int x,y;
        cin>>x>>y;
        sum+=max(a[x],a[y]);//利用公式
    }
    cout<<sum;
    return 0;
}