Node 정리

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include <stdio.h>

#define MAX_ARR_SIZE 100010

int N;

int res,a;

int rear, front;

 

int childCount[MAX_ARR_SIZE];

int childIdx[MAX_ARR_SIZE];

int* childs[MAX_ARR_SIZE];

int pool[MAX_ARR_SIZE];

int parent[MAX_ARR_SIZE];

int level[MAX_ARR_SIZE];

int pos[MAX_ARR_SIZE];

long long dist[MAX_ARR_SIZE];

int queue[MAX_ARR_SIZE];

void initqueue(){

    rear=front=0;

}

void pushqueue(int n){

    queue[rear] = n;

    rear = ++rear%MAX_ARR_SIZE;

}

int popqueue(){

    int n = queue[front];

    front = ++front%MAX_ARR_SIZE;

    return n;

}

void bfs(){

    int count = 0;

    while (rear != front){

        int n = popqueue();

        pos[n] = count++;

        for (int i = 0; i < childCount[n]; i++)

        {

            pushqueue(childs[n][i]);

        }

         

    }

}

void initlist(int N){

    parent[1] = -1;

    level[1] = 0;

    childs[1] = pool;

    for (int i = 1; i <= MAX_ARR_SIZE; ++i)

        childCount[i] = childIdx[i] = dist[i] = 0;

 

}

long long getDis(int from, int to){

    int max = 0;

    if (level[from] == level[to])//same level

    {

        for (int i = pos[parent[from]]; i < pos[parent[to]]; i++)

        {

            if (max < dist[i]) max = dist[i];

        }

        dist[pos[from]] = max + 2;

    }

    else{

        for (int i = pos[parent[to]]; i < pos[from]; i++)

        {

            if (max < dist[i]) max = dist[i];

        }

        dist[pos[from]] = max + 1;

    }

    return dist[pos[from]];

}

int main(){

    int tc;

 

    scanf("%d", &tc);

    for (int tci = 0; tci < tc; tci++)

    {

        initqueue();

        scanf("%d", &N);

        initlist(N);        

         

        for (int i = 2; i <= N; i++)

        {

            scanf("%d", &parent[i]);

             

            ++childCount[parent[i]];

            level[i] = level[parent[i]] + 1;

 

        }

        for (int i = 2; i <= N; i++)

        {

            childs[i] = childs[i - 1] + childCount[i - 1];

            childs[parent[i]][childIdx[parent[i]]++] = i;

 

        }

        pushqueue(1);

        bfs();

        long long result = 0;

        for (int i = 1; i <N ; i++)

        {

            result += getDis(queue[i - 1], queue[i]);

        }

        printf("%lld\n", result);

    }

    return 0;

}