摘要
Title: 1207. 大臣的旅费
Tag: 树的直径、BFS、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

1207. 大臣的旅费

题意

见原题
思路

题目意思就是求一条树上最长路——树的直径
可以采用树形dp、DFS、BFS来做
- DFS、BFS做法：
  1、任取一点x
  2、找到距离x最远的点y
  3、从y开始遍历，找到离y最远的点，与y最远的点的距离是树的直径
- 树形dp
  - 我们记录当1为树的根时，每个节点作为子树的根向下，所能延伸的最远距离d1，和次远距离d2 ，那么直径就是所有d1 + d2的最大值。

代码

DFS 大数据依然爆栈

'''
Author: NEFU AB-IN
Date: 2022-03-29 21:06:30
FilePath: \ACM\Acwing\1207.py
LastEditTime: 2022-03-29 21:06:31
'''
import sys

sys.setrecursionlimit(int(2e9))

N = int(1e5 + 10)
g = [[] for _ in range(N)]
dist = [0] * N


def dfs(u, fa, dis):
    dist[u] = dis
    for v, w in g[u]:
        if v == fa: continue
        dfs(v, u, dis + w)


n = int(input())
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])

dfs(1, -1, 0)
u = 1
for i in range(1, n + 1):
    if dist[i] > dist[u]:
        u = i

dfs(u, -1, 0)
for i in range(1, n + 1):
    if dist[i] > dist[u]:
        u = i

w = dist[u]
print(10 * w + w * (w + 1) // 2)

BFS

from collections import deque


N = int(1e5 + 10)
g = [[] for _ in range(N)]
dist = [0] * N

def bfs(u, fa, dis):
    q = deque()
    q.appendleft([u, fa, dis])
    while q:
        u, fa, dis = q.pop()
        dist[u] = dis
        for v, w in g[u]:
            if v == fa: continue
            q.appendleft([v, u, dis + w])

n = int(input())
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])

bfs(1, -1, 0)
u = 1
for i in range(1, n + 1):
    if dist[i] > dist[u]:
        u = i

bfs(u, -1, 0)
for i in range(1, n + 1):
    if dist[i] > dist[u]:
        u = i

w = dist[u]
print(10 * w + w * (w + 1) // 2)

树形dp

import sys
sys.setrecursionlimit(int(2e9))

N = int(1e5 + 10)
g = [[] for _ in range(N)]
dist1, dist2 = [0] * N, [0] * N
ans = 0

def dfs(u, fa):
    global ans
    for v, w in g[u]:
        if v == fa:
            continue
        dfs(v, u)
        dis = dist1[v] + w
        if dis > dist1[u]:
            dist2[u] = dist1[u]
            dist1[u] = dis
        elif dis > dist2[u]:
            dist2[u] = dis
    ans = max(ans, dist1[u] + dist2[u])

n = int(input())
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u].append([v, w])
    g[v].append([u, w])

dfs(1, -1)

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

1207. 大臣的旅费

题意

思路

代码