1517-RE.cpp

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
#include <cassert>

int main() {
    freopen("input.txt", "rt", stdin);

    // Чтение количества вершин и степени дерева:
    int nVert, degree;
    scanf("%d %d", &nVert, &degree);

    // Список смежностей под ребра дерева:
    std::vector<std::vector<int>> edges(1+nVert, std::vector<int>());

    // Чтение ребер:
    for (int b = 2; b <= nVert; ++b) {
        int a;
        scanf("%d", &a);
        edges[a].push_back(b);
    }

    // Обход всех вершин с подсчетом величин двух максимальных путей до листьев из каждой вершины:
    std::vector<std::pair<int, int>> height(1+nVert, {-1, -1});

    // Рекурсивная функция обхода вершины curr:
    std::function<int(int)> visit = [&](int curr) {
        // Среди всех путей до листьев из текущей вершины вниз нужно найти два максимальных
        std::vector<int> temp{0, 0};
        // Посещаем всех сыновей, сохраняя полученные от них результаты:
        for (auto & next : edges[curr]) {
            temp.push_back(1+visit(next));
        }
        // Сортируем вектор из результатов:
        std::sort(temp.begin(), temp.end(), std::greater<int>());
        // Записываем ответ для текущей вершины, выбирая два максимума:
        height[curr] = {temp[0], temp[1]};
        return temp[0];
    };

    // Запуск рекурсивного обхода дерева начиная с корня:
    visit(1);

    // Вычисление ответа:
    int64_t max = (height[1].first+1LL) * degree;
    for (int v = 1; v <= nVert; ++v) {
        if (height[v].first && height[v].second) { // Если из текущей вершины два или более путей до листьев
            max = std::max(max, (degree-1LL) * 2 * (height[1].first+1)+ height[v].first + height[v].second + 1);
        }
    }

    // Вывод ответа:
    printf("%I64d", max);

    return 0;
}