Submission #3948405

Source Code Expand

#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL mod = 1000000007;
std::vector<std::vector<LL>>G, memo;

LL dp(LL i, bool f, LL p)
{
	if (memo[i][f] != -1) return memo[i][f];
	LL res1 = (f ? 1 : 0), res2 = 1;
	for (auto v : G[i])
	{
		if (v == p) continue;
		(res1 *= dp(v, false, i)) %= mod;
		(res2 *= dp(v, true, i)) %= mod;
	}
	return memo[i][f] = (res1 + res2) % mod;
}

int main()
{
	LL N;
	in >> N;
	std::vector<LL>x(N - 1), y(N - 1);
	rep(i, N - 1) in >> x[i] >> y[i];

	G.resize(N + 1);
	rep(i, N - 1)
	{
		G[x[i]].push_back(y[i]);
		G[y[i]].push_back(x[i]);
	}

	memo.resize(N + 1);
	rep(i, memo.size()) memo[i].resize(2, -1);
	out << dp(1, true, -1) << std::endl;
}

Submission Info

Submission Time
Task P - Independent Set
User Bwambocos
Language C++14 (GCC 5.4.1)
Score 100
Code Size 808 Byte
Status AC
Exec Time 101 ms
Memory 21120 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 20
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15
Case Name Status Exec Time Memory
0_00 AC 1 ms 256 KiB
0_01 AC 1 ms 256 KiB
0_02 AC 1 ms 256 KiB
0_03 AC 1 ms 256 KiB
1_00 AC 1 ms 256 KiB
1_01 AC 101 ms 21120 KiB
1_02 AC 80 ms 13556 KiB
1_03 AC 81 ms 13428 KiB
1_04 AC 84 ms 13564 KiB
1_05 AC 85 ms 13696 KiB
1_06 AC 83 ms 13952 KiB
1_07 AC 84 ms 13568 KiB
1_08 AC 88 ms 13312 KiB
1_09 AC 88 ms 13184 KiB
1_10 AC 88 ms 13056 KiB
1_11 AC 88 ms 13056 KiB
1_12 AC 84 ms 12800 KiB
1_13 AC 86 ms 13568 KiB
1_14 AC 91 ms 15360 KiB
1_15 AC 97 ms 17920 KiB