DZY Loves Connecting

2
1
5
1
2
2
3

1
42

Hint
In the second sample, the 4 edges are (1,2),(2,3),(2,4),(3,5). All the connected sets are {1},{2},{3},{4},{5},{1,2},{2,3},{2,4},{3,5},{1,2,3},{1,2,4},{2,3,4},{2,3,5},{1,2,3,4},{1,2,3,5},{2,3,4,5},{1,2,3,4,5}.

If you need a larger stack size, 
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
 

一个挺直接的树DP。之前TC的一个原题，。比赛时死活没啃出来。。

。太嫩了……

题目大意：给出一个树，详细建法就不细说了。每一个点贡献为1，问树上全部不同集合的合计贡献。

首先对于每一个点，我们能够求出它所在的集合数量。

开个数组cnt。表示第i个点在其子树中所在的集合数。这样cnt[i]就等于i全部孩子的cnt+1的乘积。事实上这里用到了组合，从全部孩子中能够随意选择一定的集合(+1表示空集)进行组合。

求出集合数是为了求贡献，遍历到i的某个孩子的时候，新添加的贡献事实上就是之前的全部贡献乘上该孩子的集合数+1(选择某些集合组合)，然后对于之前遍历的子数。该孩子也能够提供贡献，也就是该孩子的贡献乘上当前出现的集合数。

口述表达的不好，也不会做那种图。

。还是看代码吧，就俩公式。。

代码例如以下：

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8;

struct Edge
{
	int v,next;
};

Edge eg[233333];
int head[233333];
//0存当前节点往下包括当前节点的区间数 1存当前节点的子树中全部包括当前节点的贡献
LL dp[233333][2];
LL ans;

void dfs(int u)
{
	dp[u][1] = 1;
	dp[u][0] = 1;
	for(int i = head[u]; i != -1; i = eg[i].next)
	{
		dfs(eg[i].v);
		//当前点子树中包括当前点的区间的贡献
		dp[u][1] = (dp[u][1]*(dp[eg[i].v][0]+1)+dp[eg[i].v][1]*dp[u][0])%mod;
		dp[u][0] = (dp[u][0]*(dp[eg[i].v][0]+1))%mod;
	}
	ans = (ans+dp[u][1])%mod;
}

int main()
{
	//fread();
	//fwrite();

	int x,t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		memset(head,-1,sizeof(head));
		for(int i = 2; i <= n; ++i)
		{
			scanf("%d",&x);
			eg[i].v = i;
			eg[i].next = head[x];
			head[x] = i;
		}
		ans = 0;
		dfs(1);
		printf("%lld\n",ans);
	}

	return 0;
}