题意简述

给定 个点的一棵树，点有点权。有两个人在树上染色，先手后手轮流染黑白两色，最后的得分是自己染的点权和 + 两端均为自己的颜色的边权和。 求先手的得分与后手的得分之差。保证 为偶数。

解题思路

这题的代码仅仅有 46 行 1.1k，却被洛谷评为黑色，原因就是它的思维难度较高。

一个小 trick：将边权转移到点权上。

形式化地，定义 为 点原来的点权， 为 边的边权，则新的点权 为：

通俗地讲，我们把一条边的边权分成两半，分别加入两个端点的点权，形成了新的点权。

拥有了新的点权，就可以直接贪心取点：先手取新点权第一、三、五、七……大的，后手取新点权第二、四、六、八……大的。

这是个很不显然的 trick，接下来会给出简要证明。

首先我们考虑一种简单的情况，有三个点两条边 。

1. 先手染了 后手染了 ：

2. 先手染了 ，后手染了

可以显然看出这两种情况都是成立的。

将它推广一下，就可以得到上面的做法是成立的。

代码实现

超级简单。
有一点小细节在代码里说了。

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

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl;
#define forall(G,u) for (int i_ = 0, __for_siz__ = (int) G[u].size(); i_ < __for_siz__; ++i_) 

using std::cin;
using std::cout;
using std::endl;

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 10000 + 10;

int n, m;
int wt[MAXN];

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; ++i) {
        wt[i] = ((read()) << 1);
        // 一会要把边权均分到两条边里
        // 为了避免除以二 这里先乘二 最后再除以二
    }
    for (int i = 1; i <= m; ++i) {
        int a = read(); int b = read(); int c = read();
        // 将边权均分到两条边中
        wt[a] += c; wt[b] += c;
    }
    std::sort(wt + 1, wt + 1 + n, std::greater<int>());
    long long int ans = 0;
    for (int i = 1; i <= n; i += 2) {
        ans += wt[i] - wt[i + 1];
    }
    printf("%lld\n", (ans) >> 1);
    return 0;
}