松坡将军
此为蓝桥杯2015校内选拔第七题：
G将军有一支训练有素的军队，这个军队除开G将军外，每名士兵都有一个直接上级（可能是其他士兵，也可能是G将军）。现在G将军将接受一个特别的任务，需要派遣一部分士兵（至少一个）组成一个敢死队，为了增加敢死队队员的独立性，要求如果一名士兵在敢死队中，他的直接上级不能在敢死队中。请问，G将军有多少种派出敢死队的方法。注意，G将军也可以作为一个士兵进入敢死队。输入格式：输入的第一行包含一个整数n，表示包括G将军在内的军队的人数。军队的士兵从1至n编号，G将军编号为1。接下来n-1个数，分别表示编号为2, 3, ..., n的士兵的直接上级编号，编号i的士兵的直接上级的编号小于i。输出格式：输出一个整数，表示派出敢死队的方案数。由于数目可能很大，你只需要输出这个数除10007的余数即可。
样例输入1
3
1 1
样例输出1
4
样例说明
这四种方式分别是：1. 选1；2. 选2；3. 选3；4. 选2, 3。
样例输入2
7
1 1 2 2 3 3
样例输出2
40
解此题的思路如下：依照题目，下属的直接上属不能进入敢死队，依照下图，程序最终要求的是将右边树的叶子子节点个数求出，再减去所有人都不来的一种情况即可。
下面的程序，对于取余数的部分处理的不是很好，应该可以通过的数据范围有限，取余数的有个离散数学的什么定理好像是能解决的，因能力有限，还未掌握。。
子函数基本流程：
1、每次计数一次的条件，到达依据士兵编号记录上属的一维数组a[100001]的尾部,count++
2、若此士兵已被访问，则调用dfs，访问下一位士兵
3、若此士兵未被访问，则将其分为来与不来两种情况（被访问意味着不能再次被访问，包括两种情况，情况1为编号为i的士兵来或不来，此时visited[i]=1,情况2为士兵I为某个要来直接上属的下属是，此时visited[i]=2）
具体C代码如下，编译通过的环境为DEV-C++：
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
static int count; //定义全局静态变量，记录总的情况数
void dfs(int a[100001], int visited[100001], int i){
if (a[i] == -1){ //每次计数一次的条件，到达依据士兵编号记录上属的一维数组a[100001]的尾部,count++
count++;
return;
}
if (a[i] != -1 && visited[i] >= 1){ //若此士兵已被访问，则调用dfs，访问下一位士兵
dfs(a, visited, ++i);
}
if (a[i] != -1 && visited[i] == 0){ //若此士兵未被访问
visited[i] = 1; //此士兵来时
for (int j = 0; a[j] != -1; j++){ //其下属均将visited[j]=2，作为已被访问
if (a[j] == i){
visited[j] = 2;
}
}
dfs(a, visited, ++i);
i--; //此士兵不来时，首先将上面假设他来的数据变回未方式的状态
for (int j = 0; a[j] != -1; j++){
if (a[j] == i)
visited[j] = 0;
if (i < j && visited[j]==1) //此处需注意，标号为1的，且i<j的才能恢复原状，而标号为2且i<j的不能恢复原状
visited[j] = 0;
}
dfs(a, visited, ++i);
}
}
int main()
{
int n, a[100001], i = 0, j = 1, visited[100001] = { 0 };
char temp[100000];
a[0] = -2;
scanf("%d", &n);
if(n!=1&&n>0){ //输入格式控制
getchar();
while (1){
temp[i++] = getchar();
if (temp[i - 1] == ' '){
temp[i - 1] = '\0';
a[j++] = atoi(temp) - 1;
strcpy(temp, "");
i = 0;
}
if (temp[i - 1] == '\n'){
temp[i - 1] = '\0';
a[j++] = atoi(temp) - 1;
strcpy(temp, "");
i = 0;
break;
}
}
a[j] = -1;
dfs(a, visited, i);
printf("%d", (count - 1) % 10007);
}
if(n==1){ //考虑只有将军一人的情况
printf("%d", n);
}
if(n<0){
printf("Unvalid input!");
}
return 0;
}