#include <stdio.h>

const int FRANCE_KING = 0;
const int ENGLAND_KING = 1;

struct Surbordinate
{
    Surbordinate(int value_, Surbordinate* next_) : next(next_), value(value_) {}
    int value;
    Surbordinate* next;
};

class Surbordinates
{
public:
    Surbordinates()
    {
        Head = NULL;
    }

    void add(int value)
    {
        if(Head == NULL)
        {
            Head = new Surbordinate(value, NULL);
        }
        else
        {
            Surbordinate* current = Head;
            while(current->next != NULL)
                current = current->next;

            Surbordinate* newNode = new Surbordinate(value, NULL);
            current->next = newNode;
        }
    }

public:
    Surbordinate* Head;
};

struct Lord
{
    Lord() { side = -1; myLord = -1; }
    Surbordinates surbordinates;
    int myLord;
    int side;
};

void changeLord(Lord* lordary, int n)
{
    if(lordary[n].side == ENGLAND_KING)
    {
        lordary[n].side = FRANCE_KING;
    }
    else
    {
        lordary[n].side = ENGLAND_KING;
    }

    Surbordinate* current = lordary[n].surbordinates.Head;
    while(current != NULL)
    {
        changeLord(lordary, current->value);
        current = current->next;
    }
}

int main()
{
    //태스트 케이스 T
    int testNum = 0;
    scanf("%d", &testNum);

    while(testNum-- > 0)
    {
        //귀족의 수 N입력
        int aristocratNum = 0;
        scanf("%d", &aristocratNum);

        //질문의 개수 Q입력
        int questionNum = 0;
        scanf("%d", &questionNum);

        //귀족의 수 만큼 배열 할당
        Lord* lordAry = new Lord[aristocratNum];
        
        //귀족의 군종관계 입력
        //각 나라의 왕은 입력하지 않기때문에 -2만큼...
        for(int i=0; i<aristocratNum-2; ++i)
        {
            int a,b;
            scanf("%d %d", &a, &b);

            lordAry[a-1].surbordinates.add(b-1);
            lordAry[b-1].myLord = a-1;
        }

        //영국과 프랑스로 팀을 나눈다
        for(int i=0; i<aristocratNum; ++i)
        {
            switch(i)
            {
            case 0:
                lordAry[i].side = FRANCE_KING;
                break;
            case 1:
                lordAry[i].side = ENGLAND_KING;
                break;
            default:
                {
                    int myLord = i;
                    while(!(myLord == ENGLAND_KING || myLord == FRANCE_KING))
                    {
                        myLord = lordAry[myLord].myLord;
                    }
                    lordAry[i].side = myLord;
                }
                break;
            }
        }

        //질문을 받으면서 팀을 변경한다
        //귀족이 나라를 배신했을때 그 아랫 귀족까지 배신되도록
        //재귀를 이용한다.
        for(int i=0; i<questionNum; ++i)
        {
            char c;
            getchar();
            scanf("%c", &c);
            switch(c)
            {
            case 'T':
                {
                    int n;
                    scanf("%d", &n);
                    
                    //재귀 사용
                    changeLord(lordAry, n-1);
                }
                break;
            case 'Q':
                {
                    int a,b;
                    scanf("%d %d", &a, &b);
                    if(lordAry[a-1].side == lordAry[b-1].side)
                    {
                        printf("Ally\n");
                    }
                    else
                    {
                        printf("Enemy\n");
                    }
                }
                break;
            }
        }
    }
}

위에와 같이 했고, 예제 답 혹은 그 이상으로 저만의 테스트 데이터를 만든 후에 검증을 해봤지만 다 알맞게 나왔습니다. 하지만 계속해서 시간초과라고 뜨고 답답합니다.

5시간 현재 붙잡고있습니다.

어디서 문제인지 힌트라고 주시면 정말 감사하겠습니다. ㅠㅠ

100YEARSWAR 문제를 제가 풀어보려고 노력한것입니다.

댓글의 조언에 따라 위에 코드 주석 하나하나 달았습니다.

코드 설명입니다.

전체 귀족 수 크기의 배열을 생성합니다.
각 원소들은 해당 귀족과 일치합니다.
0은 프랑스왕이며 1은 영국왕입니다.
각 원소는 Lord(영주)라는 구조체로 만들어져있는데,
자기 직속 휘하 귀족이 몇명있는지를 알수 있습니다.
(Subordinate 변수, 링크드 리스트를 이용한다.)
또한 각각의 직속 상관 귀족이 누구인지도 알 수 있습니다. (myLord 변수)
예를 들어 예제에서
1 3
2 4
3 5
이면 1의 직속 휘하 귀족은 3이며 3의 직속 휘하 귀족은 5입니다.
또한 3의 직속 상관 귀족은 1입니다.

각각의 원소는 side라는 변수로 영국 혹은 프랑스국 동맹국인지 알 수 있습니다.

changeLord를 통해서 재귀를 통해 반란된것을 표시합니다.
예를 들어 T 3을 하면 귀족 3 및 3의 포함된 모든 귀족은 자기 국가를 바꿉니다. (not과 같이)

이런식으로 했는데 되지 않습니다. ㅠㅠ
또 설명해드릴부분 있는지 알려주시면 상세히 알려드리겠습니다.

부탁드립니다. ㅠㅠ