蓝桥杯 --- G将军 （伪树形DP）

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;}