1517-accepted.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) {
        // Среди всех путей до листьев из текущей вершины вниз нужно найти два максимальных
        int max1 = 0, max2 = 0;
        // Посещаем всех сыновей, обновляя максимумы:
        for (auto & next : edges[curr]) {
            int temp = 1 + visit(next);
            if (temp > max1) {
                max2 = max1;
                max1 = temp;
            } else if (temp > max2) {
                max2 = temp;
            }
        }
        // Записываем ответ для текущей вершины:
        height[curr] = {max1, max2};
        return max1;
    };

    // Запуск рекурсивного обхода дерева начиная с корня:
    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;
}