题解 P7162 【[COCI2020-2021#2] Sjekira】

tommymio · 2021-03-05 19:38:38 · 题解

两种做法。一种 O(n \log n)，另一种是 O(n)。

这个题显然考虑贪心。每次从连通块大小不为 1 的连通块中删去一个最大的点是最优的，因为我们希望权值大的点尽可能少的被计入答案。那我们逆序模拟这个过程就好了。具体来说将所有点按权值从小到大排序，考虑加入每个点 x 和它的连边，如果它的出边指向的 y_i 已加入，那么就合并 x 与 y_i 所在的连通块。这个过程中使用 \text{dsu} 维护连通块权值最大值即可。算法瓶颈在排序处 O(n\log n)。

第二种做法更有意思一点。我们尝试把贪心得到的值写成一个表达式：

证明如下：考虑任意一棵子树 T，第一个删除的点是 T 中的 x 点，它在 T 中权值是最大的。那么，设 id_i 为以 i 为根的子树内取到点权最大值的点的编号，则删去 x\to y_k 这条边的花费为 val_x+val_{id_{y_k}}。我们注意到 val_x 会作为边上两点权值 \max 被计入答案，并且每个 T 内的点只会以非 \max 的形式被计入一次（举例：处理以 id_{y_k} 为根的子树统计答案时不再会将 x 与 id_{y_k} 以非 \max 的形式计入）。于是证毕。

直接计算此式即可。时间复杂度为 O(n)。

此处只贴上第一种做法的代码，第二种这么简单大家都会写吧（

#include<cstdio>
#include<vector>
#include<algorithm>
typedef long long ll;
int cnt=0;
std::vector<int> vec[100005];
int maxn[100005],vis[100005],fa[100005],id[100005]; 
inline int read() {
    register int x=0,f=1;register char s=getchar();
    while(s>'9'||s<'0') {if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
    return x*f; 
}
inline int max(const int &x,const int &y) {return x>y? x:y;}
inline int find(int x) {return x==fa[x]? x:fa[x]=find(fa[x]);}
inline bool cmp(int x,int y) {return maxn[x]<maxn[y];}
int main() {
    int n=read(); ll ans=0;
    for(register int i=1;i<=n;++i) maxn[i]=read(),fa[i]=id[i]=i;
    std::sort(id+1,id+1+n,cmp);
    for(register int i=1;i<n;++i) {int x=read(),y=read(); vec[x].push_back(y); vec[y].push_back(x);}
    for(register int i=1;i<=n;++i) {
        int x=id[i]; vis[x]=1;
        for(register int k=0;k<vec[x].size();++k) {
            int y=vec[x][k]; if(!vis[y]) continue;
            int fx=find(x),fy=find(y);
            if(fx!=fy) {
                ans+=maxn[fx]+maxn[fy];
                maxn[fx]=max(maxn[fx],maxn[fy]);
                fa[fy]=fx;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}