题意

给定$n$个节点的树，每一节点上均有一个属性$h_i$。初始时每一节点的权值都为$0$，你可以给花费$e$点代价给某一结点增加$e$的权值。请问，若要使任意节点$w$，均存在一条从$u$到$v$且经过$w$（$w$可以为$u$或$v$）的简单路径，使其满足$min(u_e, v_e) \geq h[w]$，所需的最小代价是多少？

思路

考虑从最特别的点入手。以下为本题最关键的转化之处：本题中可以选择$h[i]$最大的一个点作为根节点。

由于根节点的$h[i]$最大，并且满足题意经过根节点的简单路径必然跨越两颗根节点儿子为根的子树，可以知道对于某一根节点的儿子为根的子树中的其他节点$u$，只要子树中比$u$深度更大的某一点$v$的权值$v_e$，大于等于$h[u]$，便必然存在一条路径满足题目所讲的条件。

这样转化问题后，我们发现在这种情况下，以$h[i]$最大的节点为根节点的树中，必然要为叶子节点增加权值。因此我们考虑贪心地为叶子节点赋值。

在开始的时候我的思路稍稍走偏了，写了一个错误的贪心：将每个点的儿子根据$h[i]$​的大小进行排序，然后依次访问，并维护以$u$为根的子树，所有叶子节点的最大值$ans[u]$。最后判断根节点的儿子$v$为根的子树的最大值，是否有两个及以上满足条件$ans[v] \geq h[rt]$，若无则通过维护$ans[v], v \in rt_{son}$的最大值和次大值来求解需要补充的最小代价为多少。

虽然很容易HACK，但非常诡异的是我居然通过了前八个测试点喜提wa9，甚至当时我还觉得是不是差一点A了

代码（错误的贪心）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

int n, h[maxn], cnt, ans[maxn], isf[maxn], rt = -1, rmx = -1, maxx;
vector<int> G[maxn];
void dfs(int x, int fa){
    int flag = 0;
    if(x != rt){
        maxx = max(maxx, h[x]);
    }
    for(auto nx : G[x]){
        if(nx == fa)    continue;
        flag = 1; 
        dfs(nx, x);
        ans[x] = max(ans[x], ans[nx]);
    }
    if(!flag){
        isf[x] = 1;
        ans[x] = max(h[x], maxx);
        maxx = 0;   
    }
}
signed main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(int i = 1; i <= n - 1; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        if(h[i] > rmx || (h[i] == rmx && G[i].size() > G[rt].size())){
            rmx = h[i]; rt = i;
        }
    }
    for(int i = 1; i <= n; i++){
        sort(G[i].begin(), G[i].end(), [&](int a, int b){return h[a] > h[b];});
    }
    dfs(rt, 0);
    int cntt = 0, res = 0, fir = 0, sec = 0;
    for(auto x : G[rt]){
        if(ans[x] == rmx)    cntt++;
        if(ans[x] > fir){
            sec = fir;
            fir = ans[x];
        }
        else if(ans[x] > sec){
            sec = ans[x];
        }
    }
    for(int i = 1; i <= n; i++){
        if(isf[i])    res += ans[i];
    }
    if(cntt == 0)    res += (rmx - fir) + (rmx - sec);
    if(cntt == 1)    res += (rmx - sec);
    cout << res << '\n';
    return 0;
}

Hack数据

输入

1
2
3
4
5
6
7
8
7
9 5 2 1 4 9 9
1 2
2 3
2 4
4 5
4 7
1 6

输出

1
24

事实上，后半段思路是对的，但是前半段为每一节点赋值的部分所用到的贪心策略毫无疑问是错误的。

对于原代码，只要稍作修改就可以了：由叶子节点往上传已遍历到的叶子节点当前的最大值$mx$，若出现某一点$u$，使得$h[u] > mx$，说明原先的叶子节点的权值不够大，只需要选出最大权值的叶子节点加上差值$delta = h[u] - mx$，再将最大的叶子节点更新为$mx = mx + delta$即可。

如果要顺便求出根节点的儿子中的最大值和次大值，也可以在dfs中利用pair<int,int>进行便捷求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx", "sse2")
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;

int n, h[maxn], ans, rt = -1, rmx = -1;
vector<int> G[maxn];
pair<int, int> dfs(int x, int fa){
    int mx1 = 0, mx2 = 0;
    for(auto nx : G[x]){
        if(nx == fa)    continue;
        int mx = dfs(nx, x).first;
        if(mx > mx1)        mx2 = mx1, mx1 = mx;
        else if(mx > mx2)   mx2 = mx;
    }
    if(fa){
        int tp = max(0LL, h[x] - mx1);
        ans += tp; mx1 += tp;
    }
    return make_pair(mx1, mx2);
}
signed main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(int i = 1; i <= n - 1; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        if(h[i] > rmx){
            rmx = h[i]; rt = i;
        }
    }
    pair<int, int> now = dfs(rt, 0);
    ans += max(0LL, rmx - now.first) + max(0LL, rmx - now.second);
    cout << ans << '\n';
    return 0;
}