G將軍有一支訓練有素的軍隊，這個軍隊除開G將軍外，每名士兵都有一個直接上級（可能是其他士兵，也可能是G將軍）。現在G將軍將接受一個特別的任務，需要派遣一部分士兵（至少一個）組成一個敢死隊，為了增加敢死隊隊員的獨立性，要求如果一名士兵在敢死隊中，他的直接上級不能在敢死隊中。請問，G將軍有多少種派出敢死隊的方法。注意，G將軍也可以作為一個士兵進入敢死隊。輸入格式輸入的第一行包含一個整數n，表示包括G將軍在內的軍隊的人數。軍隊的士兵從1至n編號，G將軍編號為1。接下來n-1個數，分別表示編號為2, 3, ..., n的士兵的直接上級編號，編號i的士兵的直接上級的編號小于i。輸出格式輸出一個整數，表示派出敢死隊的方案數。由于數目可能很大，你只需要輸出這個數除10007的余數即可。樣例輸入131 1樣例輸出14樣例說明這四種方式分別是：1. 選1；2. 選2；3. 選3；4. 選2, 3。樣例輸入271 1 2 2 3 3樣例輸出240數據規模與約定對于20%的數據，n ≤ 20；對于40%的數據，n ≤ 100；對于100%的數據，1 ≤ n ≤ 100000。資源約定：峰值內存消耗 < 256MCPU消耗  < 2000ms請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內容。所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。注意: main函數需要返回0注意: 只使用ANSI C/ANSI C++ 標準，不要調用依賴于編譯環境或操作系統的特殊函數。注意: 所有依賴的函數必須明確地在源文件中 #include <xxx>， 不能通過工程設置而省略常用頭文件。提交時，注意選擇所期望的編譯器類型。這題我看的第一眼，就感覺是個樹形DP，然后很快xjb寫出來了，然后樣例都過不了，思路是：每個節點選與不選都分別加上相應的兒子節點。。。后來想了一會，感覺方案數應該是乘法，第一下想的是父親乘以兒子？可是父親由兒子得到啊。。。然后就不想了，看了下題解，豁然開朗，每個節點，他下面的每個兒子的方案數應該乘起來啊。。又對“樹”這個數據結構更深的理解下了。。。寫法也很好。。

這個題跟樹形DP寫法差不多，只不過不是dp，只是個遞推而已，其實樹一半都這么寫吧。。只不過我刷的樹的題太少了

注釋是一開始想用記憶化優化下，以防止數據量特別大

#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;const int Mod = 10007;const int maxn = 1e5;long long dp[maxn][3], dp1[maxn];vector<int> v[maxn];void dfs(int x){//    if(dp1[x] != -1) return dp1[x];//    long long ans = 0;//    if(!v[x].size())//    {//        dp[x][0] = 1;//        dp[x][1] = 1;//        dp1[x] = 1;////        return dp1[x];//    }    long long t0 = 1, t1 = 1;  // t0,t1用來記錄前面兒子的乘積的。。。    for(int i = 0; i < v[x].size(); i++)    {        int to = v[x][i];        dfs(to);        t0 = (dp[to][0] + dp[to][1])*t0 % Mod;  //前面的方案數的乘積乘以當前兒子的方案數        t1 = t1*dp[to][0] % Mod;//        ans = (ans + dp[x][0] + dp[x][1]) % Mod;    }    dp[x][0] = (t0 + dp[x][0])% Mod;  //這個根節點總的方案數    dp[x][1] = (t1 + dp[x][1]) % Mod;//    return dp1[x] = ans;}int main(){    int n;    scanf("%d", &n);    memset(dp, 0, sizeof(dp));    for(int i = 2; i <= n; i++)    {        int x;        scanf("%d", &x);        v[x].push_back(i);    }    dfs(1);//    for(int i = 1; i <= n; i++)//    {//        cout << dp[i][0] << ' ' << dp[i][1] << endl;//    }    cout << dp[1][0]+dp[1][1]-1 << endl;    return 0;}
for循環暴力：因為這個題目已經說過了，每個節點的直接上司一定比他小，所以可以直接第一層到著循環，這樣他一定是下面的
#include <cstdio>#include <vector>using namespace std;int dp[100001][2],a[100001];vector<int> m[100001];int main(){int n;scanf("%d",&n);for(int i=2;i<=n;i++){scanf("%d",&a[i]);m[a[i]].push_back(i);}for(int i=n;i>0;i--){dp[i][0]=1;dp[i][1]=1;for(int j=0;j<m[i].size();j++){dp[i][1]*=dp[m[i][j]][0];dp[i][0]*=(dp[m[i][j]][0]+dp[m[i][j]][1]);dp[i][1]%=10007;dp[i][0]%=10007;}}PRintf("%d",(dp[1][0]+dp[1][1]-1)%10007);return 0;}