Submission #689988

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <string>

#include <sstream>
#include <iomanip>

#include <map>
#include <set>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <bitset>

#include <numeric>
#include <utility>
#include <functional>
#include <algorithm>
#include <complex>
#include <memory>

#include <cstdio>
#include <cstdlib>
#include <cassert>

#include <cmath>
#include <climits>
#include <cfloat>

#include <cctype>
#include <cstring>

using namespace std;

#define FOR(M_i, M_from, M_to)	for(int M_i = (M_from); M_i < (M_to); ++M_i)
#define REP(M_i, M_n)			FOR(M_i, 0, M_n)
#define FOREACH(M_ite, M_c)		for(decltype(M_c.begin()) M_ite = M_c.begin(); M_ite != M_c.end(); ++M_ite)

#define DUMP(x)			cerr << #x << " = " << (x) << endl
#define DUMP_C(M_c)		FOREACH(ite, M_c){ cerr << *ite << ", "; } cerr << endl
#define DUMP_CS(M_c)	FOREACH(ite, M_c){ cerr << *ite << " "; } cerr << endl
#define DUMP_CN(M_c)	FOREACH(ite, M_c){ cerr << *ite << endl; } cerr << endl


template<typename T>
void print_result(ostream& out, int index, const T& result)
{
	out << "Case #" << (index + 1) << ": " << result << endl;
}

void print_progress(int i) { cout << "solving #" << i + 1 << "..." << endl; }

typedef char				sbyte;
typedef unsigned char		byte;
typedef unsigned short		ushort;
typedef unsigned int		uint;
typedef long long			ll;
typedef unsigned long long ull;


struct edge_t { int from; int to; };

const int MOD = 1000000000 + 7;
int dfs(vector<int>& color, const vector<vector<int>>& list, int cur_pos, bool must_white)
{

	if(! must_white)
	{
		for(auto other : list[cur_pos])
		{
			if(color[other] == 0) { must_white = true; break; }
		}
	}

	ll w_multi = 1;
	ll b_multi = 1;
	if(must_white) { b_multi = 0; }
	for(auto other : list[cur_pos])
	{
		if(color[other] >= 0) { continue; }
		if(must_white)
		{
			color[cur_pos] = 1;
			w_multi *= dfs(color, list, other, false) % MOD;
			w_multi %= MOD;
		}
		else
		{
			color[cur_pos] = 0;
			b_multi *= dfs(color, list, other, true) % MOD;
			b_multi %= MOD;

			color[cur_pos] = 1;
			w_multi *= dfs(color, list, other, false) % MOD;
			w_multi %= MOD;
		}
	}
	color[cur_pos] = -1;
	return (int)((w_multi + b_multi) % MOD);
}

void solve(istream& in, ostream& out)
{

	int n; in >> n;
	vector<edge_t> edge_list(n - 1);
	for(int i = 0; i < n - 1; ++i)
	{
		in >> edge_list[i].from >> edge_list[i].to;
		--edge_list[i].from;
		--edge_list[i].to;
	}

	vector<vector<int>> adj_list(n);
	for(auto& info : edge_list)
	{
		adj_list[info.from].push_back(info.to);
		adj_list[info.to].push_back(info.from);
	}

	vector<int> color(n, -1);
	int result = dfs(color, adj_list, 0, false);
	out << result << endl;
}

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	if(argc == 2)
	{
		ifstream in(argv[1]);
		string out_path = argv[1];
		out_path += ".result";
		ofstream out(out_path);
		solve(in, out);
	}
	else
	{
		solve(cin, cout);
	}
	return 0;
}

Submission Info

Judge Result