[Codeforces1084D] The Fair Nut and the Best Path（树DP）

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://codeforces.com/contest/1084/problem/D

有一棵树，每一个点和边都有权值。一个人希望从一个点走到另一个点，要求在走的过程中点权和不小于边权和。求最大的点权和与边权和之差。

首先可以知道的是，如果两个点之间是任意可达的话，那么走这两个点的时候点权和与边权和之差一定比只选中单个点更大；如果两个点中有一个点比边权小，那选最大的那一个点的收益一定会比全选要更大。

所以实际上不需要考虑某一个点到另一个点不可达的情况，因为反过来即使可达那也不会是最优的，因此实际上路径是没有必要考虑逆方向的。

根据上述规则，就可以确定考虑将答案拆成两种：

一种是当前点为端点的一条链的情况，这种情况需要维护随后可以走的差值最大的链。

另一种是以当前点为中间点，分别从两个子树中走过来的情况，这时候需要同时维护差值最大和次大的链。

于是我们相当于是在选转折点，这个并且在这个转折点上选两个权值和最大的子链，使得点权和-边权和最大。就有个问题了，选子链的时候，都是从子链走向转折点，而题目中实际上是应该有一个子链走向转折点，而另一个子链是转折点走过去的。考虑最大连续子序列和，当扫到<0的前缀和时，那么会把当前的dp值设为0，和这个问题实际上是一样的，因此不需要考虑方向的问题了。

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
#include<bits/stdc++.h>
using namespace std;

using LL = long long;
using pii = pair<int,int>;
const int maxn = 300300;
LL dp1[maxn], dp2[maxn], d[maxn];
vector<pii> G[maxn];
int n;

void dfs(int u, int p) {
  dp1[u] = 0, dp2[u] = 0;
  LL a = 0, b = 0;
  for(auto x : G[u]) {
    int v = x.first, w = x.second;
    if(p == v) continue;
    dfs(v, u);
    if(dp1[v] - w > a) {
      b = a;
      a = dp1[v] - w;
    }
    else if(dp1[v] - w > b) {
      b = dp1[v] - w;
    }
  }
  dp1[u] = max(dp1[u], a+d[u]);
  dp2[u] = max(dp2[u], a+b+d[u]);
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d",&n)) {
    for(int i = 1; i <= n; i++) {
      scanf("%I64d", &d[i]);
      G[i].clear();
    }
    memset(dp1, 0, sizeof dp1);
    memset(dp2, 0, sizeof dp2);
    for(int i = 0; i < n - 1; i++) {
      int u, v, w;
      scanf("%d%d%d",&u,&v,&w);
      G[u].emplace_back(v, w);
      G[v].emplace_back(u, w);
    }
    dfs(1, -1);
    LL ret = 0;
    for(int i = 1; i <= n; i++) {
      ret = max(ret, dp2[i]);
    }
    printf("%lld\n", ret);
  }
  return 0;
}