| 比赛 | NOIP模拟赛by mzx Day2 | 评测结果 | AAAAAAAAAA | 
    | 题目名称 | 森林大礼包 | 最终得分 | 100 | 
    | 用户昵称 | ミント | 运行时间 | 2.266 s | 
    | 代码语言 | C++ | 内存使用 | 65.29 MiB | 
    | 提交时间 | 2016-10-20 21:15:30 | 
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <malloc.h>
using namespace std;
/*const int maxn = 100000 + 100;
const int mod = 1000000000 + 7;
int rank[maxn], ufs[maxn];
long long nuts[maxn];
inline int find(int x){
	if(x==ufs[x])return ufs[x];
	return ufs[x] = find(ufs[x]);
}
inline void merge(int x, int y){
	int tx = find(x), ty = find(y);
	if(rank[tx]>rank[ty]){
		ufs[ty] = tx;
		nuts[ty] = (nuts[ty] + nuts[tx]) % mod;
	}
	else {
		ufs[tx] = ty;
		nuts[tx] = (nuts[ty] + nuts[tx]) % mod;
		if(rank[tx]==rank[ty])rank[ty]++;
	}return ;
}
int main(){
	freopen("three_squirrels.in", "r", stdin);
	freopen("three_squirrels.out", "w", stdout);
	
	memset(rank, 0, sizeof(rank));
	memset(nuts, 0, sizeof(nuts));
	for(int i=0;i<maxn;i++)ufs[i] = i;
	
	nuts[0] = 1;
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		while(k--){
			int tmp;cin>>tmp;
			merge(i, tmp);
		}
		for(int i=1;i<=n;i++)cout<<nuts[find(i)]<<' ';cout<<endl;
		for(int i=1;i<=n;i++)cout<<ufs[i]<<' ';cout<<endl;
	}cout<<nuts[find(n)]%mod<<endl;
	
	return 0;
}//*/
const int maxn = 100000 + 100;
const int mod = 1000000000 + 7;
long long nuts[maxn];
bool vis[maxn];
vector<int> G[maxn];
/*inline void DFS(int u){
	vis[u] = true;
	for(int i=0;i<G[u].size();i++){
		int v = G[u][i];
		if(!vis[v])DFS(v);
		nuts[u] += nuts[v];nuts[u] %= mod;
	}return ;
}//*/
inline long long DFS(int u){
	if(vis[u])return nuts[u] % mod;
	vis[u] = true;
	for(int i=0;i<G[u].size();i++){
		nuts[u] += DFS(G[u][i]) % mod;
		nuts[u] %= mod;
	}return nuts[u];
}
int main(){
	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	
	freopen("three_squirrels.in", "r", stdin);
	//freopen("out.txt", "r", stdin);
	freopen("three_squirrels.out", "w", stdout);
	
	memset(nuts, 0, sizeof(nuts));nuts[0] = 1;
	memset(vis, false, sizeof(vis));vis[0] = true;
	
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		int k;cin>>k;
		while(k--){
			int tmp;cin>>tmp;
			G[i].push_back(tmp);
		}
	}
	cout<<DFS(n)%mod<<endl;//cout<<nuts[n]%mod<<endl;
	
	//for(int i=1;i<=n;i++)cout<<nuts[i]<<' ';cout<<endl;
	return 0;
}