Groundhog and Apple Tree。

Solution

        题面略，话说很久都没有因为一道题而单独开一篇文章了。
        在某一个节点休息（恢复HP），可以认为是它在父节点休息够了再下来，这样所有的休息操作都可以放到根节点上。
        设置一个$dp(x)$，表示到$x$子树上，至少需要多少的HP才能完整地遍历这棵树，答案就是$dp(1)$。
        注意到若按照最优决策进行，假设从某一个节点开始时HP是$x$，返回回来时是$y$，则$x-y$应是一个定值，设其为$c_i$，$c_i$可以通过下面的递推式计算得到：

        其中$son(i)$是$i$的子节点集合，$e(i,j)$是$(i,j)$边的边权，$a_i$是$i$上苹果的值。
        然后考虑如何进行$dp$的递推，主要是子节点访问顺序的问题，假设我们按照$s_1,\cdots,s_k$的顺序进行，其中$k=|son(i)|$。
        为了简化这个问题，我们先忽略$i$处的苹果，最后把它单独减去即可，然后定义一个函数$f_i$表示已经遍历了前$i-1$棵子树回到根节点$i$时的HP，这样由如下的递推关系（下面把$e(i,son_j)$简写成$e(j)$）：

        假设$f_1=x$，则简化这个式子后可以得到：

        综合来看，就有：

        这里认为$e_{k+1}+dp(k+1)=0$，于是$x$就应该为右侧的最大值，容易发现$dp(i)=\max(0,x-a_i)$。
        根据贪心相邻最优的观点，假设有$i$和$j$相邻，并假设之前的前缀和是$S$，那么不交换的两者较大值为：

        交换后就是：

        假设交换后更优，则有两种情况，第一种情况：

        它等价于：

        另一种情况：

        它等价于：

        下面证明几个观点：

若$2e_i+c_i>0$，而$2e_j+c_j<0$（$j=i+1$），则两者必交换。即满足$2e_j+c_j<0$者顺序靠前。

        首先，若$e_i+dp(i)>e_j+dp(j)$成立，则满足第一种情况，交换两者更优。
        若$e_i+dp(i)<e_j+dp(j)$，则有：

        三个式子叠加得到$dp(j)-e_j-c_j>dp(i)-e_i-c_i$，满足条件二，因此两者交换更优。

对于$2e_j+c_j<0$，$e_j+dp(j)$较小者靠前。

        这由条件一直接可以得到。

对于$2e_j+c_j>0$，$dp(j)-e_j-c_j$较大者靠前。

        这由条件二直接可以得到。
        综上我们得到了一个贪心算法，可以发现这个相邻最优的排序是可传递的，这保证了它的正确性。贪心的准则如下：

  • $2e_j+c_j<0$靠前，$2e_j+c_j>0$靠后。
  • 对于$2e_j+c_j<0$，$e_i+dp(i)$较小者靠前。
  • 对于$2e_j+c_j>0$，$dp(j)-e_j-c_j$较大者靠前。
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
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
ll dp[N], c[N];
int a[N];
struct Edge
{
    int next, to, v;
} edge[N << 1];
int n, head[N], cnt = 1;
inline void add(int x, int y, int v)
{
    edge[cnt].v = v, edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
void DFS(int x, int f)
{
    c[x] = 0;
    for (int i = head[x]; i; i = edge[i].next) {
        if (edge[i].to == f) continue;
        DFS(edge[i].to, x);
        c[x] += 2ll * edge[i].v + c[edge[i].to];
    }
    c[x] -= a[x];
}
struct Node
{
    ll ee, cc, ddp;
    bool operator<(Node s)
    {
        if (2 * ee + cc < 0 && 2 * s.ee + s.cc >= 0) return 1;
        if (2 * ee + cc >= 0 && 2 * s.ee + s.cc < 0) return 0;
        if (2 * ee + cc < 0 && 2 * s.ee + s.cc < 0) return ee + ddp < s.ee + s.ddp;
        return ddp - ee - cc > s.ddp - s.ee - s.cc;
    }
};

ll DP(int x, int f)
{
    vector<Node> vec;
    for (int i = head[x]; i; i = edge[i].next) {
        if (edge[i].to == f) continue;
        Node s;
        s.cc = c[edge[i].to], s.ee = edge[i].v, s.ddp = DP(edge[i].to, x);
        vec.push_back(s);
    }
    sort(vec.begin(), vec.end());
    ll s = 0;
    dp[x] = 0;
    for (int i = 0; i < vec.size(); i++) {
        dp[x] = max(dp[x], s + vec[i].ddp + vec[i].ee);
        s += 2 * vec[i].ee + vec[i].cc;
    }
    dp[x] = max(dp[x], s);
    dp[x] = max(0ll, dp[x] - a[x]);
    return dp[x];
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n), cnt = 1;
        for (int i = 1; i <= n; i++) scanf("%d", a + i), head[i] = 0;
        for (int i = 1, x, y, w; i < n; i++) scanf("%d%d%d", &x, &y, &w), add(x, y, w), add(y, x, w);
        DFS(1, 0);
        printf("%lld\n", DP(1, 0));
    }
    return 0;
}