G将军有一支训练有素的军队，这个军队除开G将军外，每名士兵都有一个直接上级
正在做道题的同学，可以先看一下应用知识，再思考一下这道题；
应用知识
- C语言递归
-
离散数学的二叉树的先根
不懂的，可以先去看看，不然看不懂后面讲的什么，用不了多少时间。
具体思路
题目：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；
- 选2；
- 选3；
- 选2, 3。
样例输入2
7
1 1 2 2 3 3
样例输出2
40
举一个例子来讲述我的理解
举例输入
4
1 1 2
1代表G将军
每一个人都可以分为两种情况，来与不来（图中用空和编号表示），那就有2^n情况;
题目条件：如果一名士兵在敢死队中，他的直接上级不能在敢死队中；
处理方法：遇到限制条件的图中节点，只画出不来情况；
依照题目给定的条件，将例子转变为二叉树图的形式
画图规制： - 不来永远在左边，来永远在右边；
- 遇到限制条件的图中节点，只画出不来情况（即只画左子树，不画右子树）
怎么看是否有限制条件：从该节点到开始（一条线）有没有将要写的士兵的上级
结果：为有分叉的节点的数量；
代码： 虽然用C++写的，但C语言也可看懂（有注释）
#include<iostream>
using namespace std;//C语言直接将第1、2直接改为#include<stdio.h>
int sum;//有分叉的节点数量
int a[100001];//原始数据，保存每一个士兵的直接上级
int visited[100001];//敢死队中的士兵，即1为该士兵在，0为该士兵不在
int n;//敢死队中的人数
int dfs(int visitor)
{
sum=sum%10007;//题目要求
if(visitor<n)//限制递归的进行
{
dfs(visitor+1);//左子树的进行，即该士兵不在
if(visited[a[visitor]-1]==0)//判断该士兵的直接上级在不在
{//不在即运行下面代码
visited[visitor]=1;//该士兵的状态变为1，即在
dfs(visitor+1);//右子树的进行，即该士兵在
visited[visitor]=0;//当该士兵在的情况全运行完毕，注意现在的完毕是指在现在情况下的完毕，可能有点难懂，可以看下面的图再来思考
sum++;//左子树总是存在，生成右子树，即意味分叉节点的增加；
}
}
}
int main(void)
{
cin>>n;//C语言改为scanf("%d",&n);
a[0]=1;//因为G时1号，a[0]=0的话，a[visitor]-1将为-1。当然这样赋值也是因为G将军没有直接上级这一特殊原因导致；
for(int i=1;i<n;i++)//C语言改为int i; for(i=1;i<n;i++)
cin>>a[i];//C语言改为scanf("%d",&a[i]);
dfs(0);
cout<<sum<<endl;//C语言改为printf("%d\n",sum);
return 0;
}
具体过程示意图
if(visited[a[visitor]-1]==0)
{
visited[visitor]=1;
dfs(visitor+1);
visited[visitor]=0;
sum++;
}
核心代码讲解：
- visited[a[visitor]-1]：直接上级原始数据表示与数组始终差1
- visited[visitor]=0;这段代码在图形中表示就是节点的右子树运行完毕，返回节点时的操作。即返回到节点时，要与节点的状态相同。
使用的环境为Dev C++和VS2010
因为没有测试环境，就将其他博客的代码一起同时测试同一例子和自己随机编写的例子，结果一样。结果发现：
少一点的数据21可以
但对于较大的51这样的数据，没有输出，也没有直接终止。
可能是2^51的量级太大了。。。。。
因为没有测试环境，所以也不知道自己是否正确。。。
如果有问题，请留言评论，我们一起学习！！！
参考资料
参考书籍：挑战程序设计竞赛