7-3 Size of Military Unit (25 分)

The Army is a large organization, made up of many different branches and groups. Each group is called a “unit”. The Army has a hierarchical structure (等级结构) – that is, each senior officer gives commands to many units, and the commander of a unit reports to the only senior officer who gives commands directly to him/her. There is a unique General of the Armies who holds the highest rank.

Now given the list of soldiers and their senior officers, your job is to tell the size (number of soldiers) of any specific unit.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (2≤N≤10⁵), which is the total number of soldiers in the army. Assume all the soldiers are numbered from 1 to N, and General of the Armies is always the number 1. Then the next line gives N−1 numbers, each corresponds to an officer or a soldier numbered from 2 to N. The ith number corresponds the only senior officer who gives commands directly to the ith soldier. Notice that since General of the Armies holds the highest rank and is the number 1, the above list starts from the 2nd officer/soldier.

Then a positive integer M (≤N), the number of queries, is given in a line. Followed in the next line are M numbers, each represents a soldier.

Output Specification:
For each soldier in a query, output in a line the size of his/her unit.

10
4 6 6 8 1 8 1 8 8
4
8 6 4 9

5
4
2
1

记忆化搜索，每次搜存每个点

#include  
#include 
using namespace std;
vector v[100100];
int ans[100100];
int dfs(int x) {
	for(int i = 0; i < v[x].size(); ++i)
		ans[x] += dfs(v[x][i]);
	return ans[x] = ans[x] + 1;
}
int main() {
	int n, m, x;
	scanf("%d", &n);
	for(int i = 2; i <= n; ++i) {
		scanf("%d", &x);
		v[x].push_back(i);
	}
	dfs(1);
	scanf("%d", &m);
	while(m--) {
		scanf("%d", &x);
		printf("%dn", ans[x]);
	}
}