树上独立集数量 树型DP

题目描述：

输入：

输出：

分析：

这是一道树形DP。设f[i][0]表示在选i个节点的独集数，f[i][1]表示不选第i个节点的独集数。 
很明显，每一个节点的f都是有它的子节点得到的。 
如果选了第i个节点，那么它的子节点全部不选。所以，f[i][0]就等于它的子节点f[j][1]的乘积。 
反之，不选第i个节点，那么它的子节点可以选也可以不选，f[i][1]等于它的子节点(f[j][0] +f[j][1])的乘积。 
边就用奇怪的方法维护就行了（不要告诉我你不会前向新或边集数组）。

#include<cstdio>

#include<cstring>

#include<algorithm>

const int mo=;

int n,a[][],g[],f[][];

bool bz[];

void qsort1(int l, int r)

{

    int i=l;

    int j=r;

    int x;

    int t;

    x=a[(l+r)/][];

    while (i<=j)

    {

        while(a[i][]<x) i++;

        while(a[j][]>x) j--;

        if(i<=j)

        {

            t=a[j][];

            a[j][]=a[i][];

            a[i][]=t;

            t=a[j][];

            a[j][]=a[i][];

            a[i][]=t;

            j--;

            i++;

        }

    }

    if (l<j) qsort1(l,j);

    if (r>i) qsort1(i,r);

}

void dfs(int x)

{

    int z1,z2,z=g[x],l=;

    while (a[z][]==x)

    {

        if (bz[a[z][]]==false)

        {

            l=;

            bz[a[z][]]=true;

            dfs(a[z][]);

            f[x][]=(f[x][]*f[a[z][]][])%mo;

            if (z==g[x])

            {

                z1=f[a[z][]][];

                z2=f[a[z][]][];

            }

            else

            {

                z1=(z1*f[a[z][]][]+z1*f[a[z][]][])%mo;

                z2=(z2*f[a[z][]][]+z2*f[a[z][]][])%mo;

            }

        }

        z++;

    }

    if (l==)

    {

        f[x][]=(z1+z2)%mo;

    }

}

int main()

{

    int i,j,k;

    scanf("%d",&n);

    int zl=;

    for (i=;i<=n-;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        zl++;

        a[zl][]=x;

        a[zl][]=y;

        zl++;

        a[zl][]=y;

        a[zl][]=x;

    }

    for (i=;i<=n;i++)

    {

        f[i][]=;

        f[i][]=;

    }

    qsort1(,zl);

    int z=;

    for (i=;i<=zl;i++)

    {

        if (a[z][]!=a[i][])

        {

            g[a[z][]]=z;

            z=i;

        }

    }

    g[a[z][]]=z;

    bz[]=true;

    dfs();

    printf("%d",(f[][]+f[][])%mo);

}