1517-accepted.cpp

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

const bool DEBUG = false;

std::vector<std::vector<int>> edges;

void prepare(int curr, std::vector<int>& stack) {
    stack.push_back(curr);
    for (auto & next : edges[curr]) {
        prepare(next, stack);
    }
}

int main() {
    freopen("input.txt", "rt", stdin);
    // freopen("output.txt", "wt", stdout);

    int nVert, degree;
    scanf("%d %d", &nVert, &degree);


    edges.assign(1+nVert, std::vector<int>());

    for (int b = 2; b <= nVert; ++b) {
        int a;
        scanf("%d", &a);
        edges[a].push_back(b);
    }

    if (DEBUG) {
        printf("Edges:\n");
        for (int v = 1; v <= nVert; ++v) {
            printf("\t%d:", v);
            for (auto & next : edges[v]) {
                printf(" %d", next);
            }
            printf("\n");
        }
        printf("\n");
    }

    std::vector<std::pair<int, int>> height(1+nVert, {-1, -1});

    std::vector<int> stack;

    prepare(1, stack);

    while (!stack.empty()) {
        int curr = stack.back(); stack.pop_back();
        std::vector<int> temp{0, 0};
        for (auto & next : edges[curr]) {
            assert(height[next].first != -1);
            temp.push_back(1+height[next].first);
        }
        std::sort(temp.begin(), temp.end(), std::greater<int>());
        height[curr] = {temp[0], temp[1]};
    }

    if (DEBUG) {
        for (int v = 1; v <= nVert; ++v) {
            printf("%d: %d %d\n", v, height[v].first, height[v].second);
        }
    }

    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(1LL * max, (degree-1LL) * 2 * (height[1].first+1)+ height[v].first + height[v].second + 1);
        }
    }

    printf("%I64d", max);


    return 0;
}