摘要
Title: 1078. 旅游规划
Tag: 树形dp、树的直径
Memory Limit: 64 MB
Time Limit: 1000 ms

1078. 旅游规划

题意

W 市的交通规划出现了重大问题，市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。
但由于人员不足，W 市市长决定只在最需要安排人员的路口安排人员。
具体来说，W 市的交通网络十分简单，由 n 个交叉路口和 n−1 条街道构成，交叉路口路口编号依次为 0,1,…,n−1 。
任意一条街道连接两个交叉路口，且任意两个交叉路口间都存在一条路径互相连接。
经过长期调查，结果显示，如果一个交叉路口位于 W 市交通网最长路径上，那么这个路口必定拥挤不堪。
所谓最长路径，定义为某条路径 p=(v1,v2,…,vk)，路径经过的路口各不相同，且城市中不存在长度大于 k 的路径（因此最长路径可能不唯一）。
因此 W 市市长想知道哪些路口位于城市交通网的最长路径上。
思路

题意：问哪些点在树的直径上
- 利用树形dp求出树的直径的长度，并且每个点都记录了到该点的最大值和次大值
- 判断该点是不是在树的直径的方法：
  - 遍历每个顶点，若dist1[i] + dist2[i] == ans，表示最大路径是从该点得出的
  - 对该点进行两遍dfs，一遍找最大长度路径，一遍找次大长度路径，对路径上的点进行标记

代码

'''
Author: NEFU AB-IN
Date: 2022-04-05 10:57:05
FilePath: \ACM\Acwing\1078.py
LastEditTime: 2022-04-05 10:58:50
'''
import sys

sys.setrecursionlimit(int(2e9))

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


def dfs(fa, u):
    global ans
    for v in g[u]:
        if v == fa:
            continue
        dfs(u, v)
        dis = dist1[v] + 1
        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])


def dfs1(fa, u): #遍历最大值的路径
    st[u] = 1
    for v in g[u]:
        if v == fa:
            continue
        if dist1[u] == dist1[v] + 1:
            dfs1(u, v)


def dfs2(fa, u): #遍历次大值的路径
    st[u] = 1
    for v in g[u]:
        if v == fa:
            continue
        if dist2[u] == dist1[v] + 1: #注意这里，自己的次大值，也是由别人的最大值更新过来的，往后是要求别人的最大值的，所以调用dfs1
            dfs1(u, v)


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

dfs(-1, 0)

for i in range(n):
    if ans == dist1[i] + dist2[i]:
        dfs1(-1, i)
        dfs2(-1, i)

for i in range(n):
    if st[i]:
        print(i)

1078. 旅游规划

题意

思路

代码