题解：P7162 [COCI 2020 2021 #2] Sjekira

心路历程

1. 想到贪心，最大的点一定至少被加上他的边的个数次，考虑从大到小处理，发现很困难，需要维护子树最大值，并且是无根树；
2. 想到反向，类似合并果子，因为希望大的数最后被合成连边（一旦加入就一直产生贡献了），所以考虑反向，倒着建边，正难则反，断开困难连上容易，比较常规的思路。但是发现仅仅从小到大，没有考虑树的结构，肯定是错的，然后把思路一棒子打死了；
3. 想了很久，20 min 左右，有一些猎奇但是不可能的想法，有一些时间复杂度不对的想法，觉得思考时间足够了，做不出来就需要题解启发；
4. 看题解，发现线性递推看不懂，对于排序的方法仍有疑问，想了 5 min 左右，没有理解几个问题；
5. Orz zrm0202 %%%，发现了“当前点最大”和“顺序不重要”，解决了问题；

发现就是思路变成了窗户纸，但是最后一点捅不破。技巧就是每次想清楚了，从头到尾想透了，伪代码能写了，然后再去码。这个时候思路链完整了，而且代码码起来快，交上去一发就 AC 心态也会很好。

唯一的缺点就是可能思考时间放久了，导致效率有点低下，练的题不够多，那些思考时间可能回报率比较低；

题目

有一棵 个结点的树，每个结点有一个权值，删除一条边的费用为该边连接子树中结点权值最大值之和。问以任意顺序删除树中所有边的最小花费。

对于 的数据，，。

题解

• 正着断边不容易，不仅要维护子树最大值，而且还是无根树，结构复杂，联想生成树题目“兽径管理”、扩展与并查集、容斥原理思想，考虑反向操作，从独立开始连边；
• 考虑全局最大点存在于一个连通块内的时候，连通块内其他点没有意义，所有连边的代价都由最大点承担，这是我们不想看到的；
• 我们想要最小化，意味着让大点一直孤立，越晚连接越好，因为一旦连接，就要一直产生代价，直到更大的点出现，这提升了我们代价的下限，所以考虑从点权小的开始考虑；
• 为了遵循树的结构，我们考虑连边就不能像合并果子一样自由，而是从树上的边中进行选择，此时连出去的点，可以权值更大，也可以更小，这似乎又是一个维持最小化的阻碍；
• 考虑树的边是双向的，所以现在可以从小考虑到大，将来一定可以从大考虑到小，不会遗漏这个点对，具有可行性；
• 而且这种做法具有必要性。
  考虑以下情况：
  • 是紧挨着的三个点的点权，从小到大；
  • 若我们在 的时候就连接了 ，此时 的连通块内有其他点可以连接 ；
  • 那代价 ，不满足我们“大点孤立，小点先连”的策略；
• 所以只连接出边的那一端中相对较小的点；

欸，那就有同学（比如我）要问了：

这个出边的顺序难道不会影响最终的结果吗？你可是先把一个连通块考虑进去了！

其实这个问题在想清楚刚刚的东西之后就很明显了，因为我们从小到大枚举，并且只连接小的点，那么已有连通块内的点一定不会大于当前的点。
也就是说当前的点进去之后就一手遮天，只有他提供代价。所以顺序不重要，都是已有连通块内最大的和当前点的权值求和，先加后加都被当前的点覆盖住了。

代码如下：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 1e5 + 7;

int n;
LL weight[MAXN];
vector<int> order;
vector<int> toNode[MAXN];

int anc[MAXN];
LL val[MAXN];

LL ans;
bitset<MAXN> vis;

inline void ancInit(int siz) {
    for (int i = 1; i <= siz; ++i) {
        anc[i] = i;
        val[i] = weight[i];
    }
    return;
}
inline int findAnc(int cur) {
    if (cur != anc[cur])
        anc[cur] = findAnc(anc[cur]);
    return anc[cur];
}
inline void merge(int a, int b) {
    int ancA = findAnc(a);
    int ancB = findAnc(b);
    anc[ancA] = ancB;
    val[ancB] = max(val[ancA], val[ancB]);
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> weight[i];
        order.push_back(i);
    }
    for (int i = 1; i < n; ++i) {
        int from, to;
        cin >> from >> to;
        toNode[from].push_back(to);
        toNode[to].push_back(from);
    }

    ancInit(n);
    sort(order.begin(), order.end(), [](int a, int b) {
        return weight[a] < weight[b];
    });
    for (int from : order) {
        for (int to : toNode[from])
            if (vis[to]) {
                ans += weight[from];
                ans += val[findAnc(to)];
                merge(from, to);
            }
        vis[from] = true;
    }

    cout << ans;
    return 0;
}