樹的周遊——求從第ta節點走aim步到達的節點

★實驗任務

現有一個樹形的消息通信系統，當節點 i 要發送消息時，它會查找它的子節

點，向還沒發送過消息的子節點發送消息，如果有多個這樣的子節點，則優先選

擇節點編号最小的節點，而它的子節點也以同樣的政策向下傳送消息。當節點 i

的某個子節點完成了消息發送任務後，節點 i 繼續查找剩餘還沒發送過消息的子

節點發送消息，直到節點 i 已經向所有的子節點發送過消息了，則節點 i 完成了

它的消息發送任務。

現有 q 次詢問，每次給出一個節點編号 u 和整數 k，問從節點 u 開始發送消

息，則第 k 個收到消息的節點的編号是多少，如果不存在這樣的節點，則輸出

“-1”。

★資料輸入

第一行包含兩個整數 n 和 q，表示樹中的節點數（2≤n≤2·10^5）和詢問的

次數（1≤q≤2·10^5）。

接下來的一行包含 n-1 個整數 pi（1≤i≤n-1） 表示第 i + 1 個節點的父節點

的下标（1≤pi≤i）。節點 1 是根節點。

接下來 q 行，每行兩個整數 u 和 k（1≤u, k≤n），u 是開始傳播消息的節點

編号，k 表示詢問第 k 個收到消息的節點。

★資料輸出

輸出 q 行，每行表示第 q 次詢問的節點編号，如果不存在這樣的節點，則

輸出“-1”。

輸入示例 輸出示例

9 6

1 1 1 3 5 3 5 7

3 1

1 5

3 4

7 3

1 8

1 9

輸出：

3

6

8

-1

9

4

代碼還沒還沒試過，如果沒過再來改如果過了就不改了

這裡采用兒子連結清單表示法來表示這棵樹，開一一個數組，數組元素存的内容是節點的父節點，然後又從節點引出一個兒子連結清單。

周遊方式：遞歸地周遊，當到達每個節點時，檢視有沒有兒子連結清單，有則檢視兒子節點，沒有則傳回（說明此節點是葉節點）。如此遞歸地周遊樹，這題暫時沒想出好的做法，隻能暴力模拟了≡(▔﹏▔)≡。

代碼：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef  long long ll;
typedef unsigned long long ull;
#pragma warning(disable:4996)
#define sf scanf
#define pf printf
#define sf2d(x,y) scanf("%d %d",&(x),&(y))
#define sfd(x) scanf("%d",&x)
#define sff(p) scanf("%lf",&p)
#define pfd(x) printf("%d\n",x)
#define mset(x,b) memset((x),b,sizeof(x))
/*
兒子連結清單表示法表示樹

*/

struct Node {//
	int number;//數組存的是父親位置，連結清單存的是自己的位置
	Node* next;
	Node(int num):number(num),next(0){}
	Node() :number(0), next(0) {}
};


struct Pto {
	Node *p;
	Pto() :p(0){}
};


Node head[200010];
Pto tail[200010];


void Travel(int sta, int& stp,int aim) {
	if (stp == aim) {//到達目标步數
		pfd(sta);
		return;
	}

	if (head[sta].next == 0)
		return;

	else {
		Node* p=head[sta].next;
		while (p&&stp<aim) {
			stp++;//步數加一
			Travel(p->number, stp, aim);//通路節點
			p = p->next;
		}
		
	}

	return;
}


int main(void) {
	int n, q;
	int temp;
	Node *ptr=0;
	sf2d(n, q);
	for (int i = 2; i <= n; i++) {
		sfd(temp);
		head[i].number = temp;//記錄父親  ///把temp存進i裡面
		ptr = new Node(i);//i為自己的編号
				  //把i存進temp裡面
		if (tail[temp].p == 0) {//才有第一個兒子
			head[temp].next = tail[temp].p = ptr;
			ptr->next = 0;
		}
		else {
			tail[temp].p->next = ptr;
			tail[temp].p = ptr;
			ptr->next = 0;
		}
	}

	int sta, stp,aim;
	for (int j = 0; j < q; j++) {
        sf2d(sta,aim);
		stp = 1;
		Travel(sta, stp, aim);
		if (stp < aim)
			pfd(-1);
	}

	return 0;
}