本文共 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/