1207. 大臣的旅费

方法一: 两遍dfs暴力求解

import sys

sys.setrecursionlimit(10000)

N = 100010
M = 2 * N
graph = [-1] * N
e = [0] * M
ne = [0] * M
w = [0] * M
idx = 0
max_node = -1   # 以某点出发的最远点
max_d = 0       # 以某点出发的最远距离


def add(a,b,c):
    global idx
    idx += 1
    e[idx] = b
    ne[idx] = graph[a]
    graph[a] = idx
    w[idx] = c

# 任意一颗树，从A到B的路径是唯一的
def dfs(x,fa,dist):
    global max_d,max_node
    # x: 某个点
    # fa: x的父节点
    # dist: 从起始点到该点的距离
    cur = graph[x]
    while cur != -1:
        j = e[cur]
        k = w[cur]
        if j == fa:
            cur = ne[cur]
            continue
        if max_d < dist + k:
            max_d = dist + k
            max_node = j
        dfs(j,x,dist + k)
        cur = ne[cur]


if __name__ == "__main__":
    n = int(input())
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        add(a,b,c)
        add(b,a,c)

    dfs(1,-1,0)
    dfs(max_node,-1,0)

    res = 0
    for i in range(1,max_d + 1):
        res += (i + 10)

    print(res)

方法二：树形DP

1. 思路和树的直径类似

import sys
sys.setrecursionlimit(1000000)

N = 100010
M = 2 * N
graph = [-1] * N
w = [0] * M
e = [0] * M
ne = [0] * M
idx = 0
ans = 0   # 最长距离


def add(a,b,c):
    global idx
    idx += 1
    e[idx] = b
    ne[idx] = graph[a]
    graph[a] = idx
    w[idx] = c

def dfs(u,father):
    global ans
    # 从u节点往下的最长距离
    dist = 0
    d1 = 0
    d2 = 0

    cur = graph[u]
    while cur != -1:
        j = e[cur]
        if j == father:
            cur = ne[cur]
            continue
        d = dfs(j,u) + w[cur]
        dist = max(dist,d)
        cur = ne[cur]

        if d > d1:
            d2 = d1
            d1 = d
        elif d > d2:
            d2 = d

    ans = max(ans,d1 + d2)    # 状态转移方程

    return dist



if __name__ == "__main__":
    n = int(input())
    for _ in range(n-1):
        a,b,c = map(int,input().split())
        add(a,b,c)
        add(b,a,c)

    dfs(1,-1)

    print(int(10 * ans + ans * (ans + 1) / 2))