Submission #1294546

---

Source Code Expand

#include <iostream>
#include <vector>
#define int long long
#define MOD 1000000007
using namespace std;

vector<int> G[100000];
int dp[100000][2];

int dfs(int v,int prev,int pcolor){
	if(dp[v][pcolor] != -1) return dp[v][pcolor];
	int white = 1,black = 1;
	for(int i = 0;i < G[v].size();i++){
		int to = G[v][i];
		if(to == prev) continue;
		white = white * dfs(to,v,0) % MOD;
		if(!pcolor) black = black * dfs(to,v,1) % MOD;
	}
	if(pcolor) black = 0;
	return dp[v][pcolor] = (white + black) % MOD;
}

signed main(){
	int n;
	cin >> n;
	for(int i = 0;i < n;i++){
		dp[i][0] = -1;
		dp[i][1] = -1;
	}
	for(int i = 0;i < n - 1;i++){
		int a,b;
		cin >> a >> b; a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	cout << dfs(0,-1,0) << endl;
	return 0;
}

Submission Info

Judge Result