题解 | #游历魔法王国#

读完题后感觉是比较常见的树的dfs问题。但是看完输入格式之后有点懵，这种奇怪的输入格式虽然也能用邻接表或邻接矩阵存储，但是很别扭。
看了评论区大神的解答后才知道链式前向星这种数据结构，这道题过于适合使用链式前向星来解答，很难不怀疑出题者是按照链式前向星来输入的。
主要难点就在链式前向星的使用上。关于最大数量判断，许多类似的题中也有涉及，可自行推倒。

#include <iostream>
#include <string.h>

#define MAXN 50

using namespace std;

struct node{
    int to;
    int next;
}edge[MAXN];

int len[MAXN];
int head[MAXN];
int cnt = 0;

void addEdge(int start, int end){
    edge[cnt].to = end;
    edge[cnt].next = head[start];
    head[start] = cnt++;
}

void getLen(int n){
    for(int i = head[n];~i;i = edge[i].next){
        len[edge[i].to] = len[n] + 1;
        getLen(edge[i].to);
    }
}

int main(){
    memset(head, 0xff, sizeof(head));
    memset(len, 0, sizeof(len));
    int N, L;
    cin >> N >> L;
    for(int i = 0;i < N - 1;i++){
        int start;
        int end;
        cin >> start;
        addEdge(start, i + 1);
    }
    getLen(0);
    int maxLen = 0;
    int maxId;
    for(int i = 0;i < N;i++){
        if(len[i] > maxLen){
            maxLen = len[i];
            maxId = i;
        }
    }
    if(maxLen > L){
        cout << L + 1;
    }
    else{
        if(N > maxLen + (L - maxLen) / 2 + 1){
            cout <<  maxLen + (L - maxLen) / 2 + 1;
        }
        else{
            cout << N;
        }
    }
}