本文共 1805 字，大约阅读时间需要 6 分钟。
为了解决这个问题，我们需要找到树中的两个不同的点S和T，使得表达式a(T) - a(S) - dist(S, T)的值最大化。树的结构和权值特性使得这个问题可以通过构建有向图来解决。
import sysfrom collections import dequedef main(): sys.setrecursionlimit(1 << 25) n = int(sys.stdin.readline()) a = [0] * (n + 2) for i in range(1, n+1): a[i] = int(sys.stdin.readline()) maxm = 1e5 + 5 head = [0] * (maxm + 2) nt = [0] * (maxm + 2) to = [0] * (maxm + 2) w = [0] * (maxm + 2) tot = 0 def add(x, y, z): nonlocal tot tot += 1 head[x] = tot nt[tot] = y to[tot] = y w[tot] = z def spfa(start): q = deque() q.append(start) d = [-float('inf')] * (maxm + 2) d[start] = 0 in_queue = [False] * (maxm + 2) in_queue[start] = True while q: u = q.popleft() in_queue[u] = False for i in range(head[u], -1, -1): v = to[i] if d[v] > d[u] + w[i]: d[v] = d[u] + w[i] if not in_queue[v]: q.append(v) in_queue[v] = True return d add(0, 0, 0) for i in range(1, n+1): add(0, i, -a[i]) add(n+1, n+1, 0) for i in range(1, n+1): add(i, n+1, a[i]) for i in range(1, n+1): u = nt[i] v = to[i] if u != -1 and v != -1: add(u, v, -1) add(v, u, -1) d = spfa(0) print(d[n+1])if __name__ == '__main__': main() 通过这种方法，我们能够高效地解决问题，适用于大规模数据。
转载地址：http://wdkv.baihongyu.com/