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