题解 | #送快递#

送快递

先找到最长的路径，得到路径的长度depth。那么剩下的节点还能访问的数量则要根据剩余电量来判断。

想要求出快递员最多可以送多少个用户，则需要规划出一条路径做到用最少的电量访问更多的用户。可以抽象理解为，用最短的路径访问图中最多的节点。

那么，思考一个简化的问题：

（1）从当前节点0开始做深度优先遍历，找到最长的路径称为主干path，长度为depth。从0出发，沿着path依次遍历。

（2）每次遇到一个分支就进入访问该分支的节点，访问完成后原路返回到主干path。这个过程走过的路径长度为2d，d为分支上的节点数。

（3）返回主干path后，继续向下遍历。遇到分支就回到第二步。

当走完所有节点后，对于主干path上的路径我们只走了一遍，所有分支上的路径都走了两遍。因此，遍历所有节点的最短路径为：depth+2D，depth为最长的路径主干path的长度，D为分支路径的长度。

回到送快递问题，快递员在0号位置出发，首先需要找到最长的路径path，长度为depth，然后判断剩余电量K是否大于depth。

若k<=depth，则返回1+k。这种情况沿着最长路径送快递就行。

若k>depth，则返回1+depth+(k-depth)//2。这种情况不仅需要沿着最长路径送快递，且遇到分支也需要送快递。(k-depth)为在保证快递员送完主干路径上的用户后还剩余的电量，这些电量用来为分支路径上的用户送快递。因为，送完分支上的用户还需返回，因此能送的分支用户数计算为(k-depth)//2。

def dfs(maps,cur, visited,path,max_depth):
    if len(path) > max_depth[0]:
        max_depth[0]=len(path)
    for neibor in maps[cur]:
        if visited[neibor]:
            pass
        else:
            visited[neibor] = True
            path.append(neibor)
            dfs(maps,neibor, visited,path,max_depth)
            path.pop()
            visited[neibor] = False



if __name__ == "__main__":
    line1 = list(map(int, input().split()))
    n, k = line1[0], line1[1]
    S = list(map(int, input().split()))  # S
    # 邻接表
    maps = [[] for i in range(n)]
    for i in range(n - 1):
        # (i+1)  <----------> S[i]
        if S[i] in maps[i + 1]:
            pass
        else:
            maps[i + 1].append(S[i])
        if (i + 1) in maps[S[i]]:
            pass
        else:
            maps[S[i]].append(i + 1)

    # print(maps)
    visited = [False]*n
    visited[0]=True# 0节点已经访问
    path = [0]
    max_depth = [1]
    # print(distance[0])
    dfs(maps,0, visited,path,max_depth)
    max_depth = max_depth[0]-1
    # print(path)
    if k <=max_depth:
        print(k+1)
    else:
        print(min(n,max_depth +1+ (k-max_depth)//2))