Submission #4119249


Source Code Expand

Copy
#include <iostream>
#include <vector>
using namespace std;

constexpr int MAX_N = 1e5 + 1;
constexpr int MOD = 1e9 + 7;

using int64 = int64_t;
#define int int64

vector<int> edge[MAX_N];
int memo_f[MAX_N];
int memo_g[MAX_N];

int f(int, int);
int g(int, int);

int g(int x, int parent){
	if(memo_g[x] > 0) return memo_g[x];
	
	int cnt = 1;
	for(auto &&child: edge[x]){
		if (child == parent) continue;
		
		(cnt *= f(child, x) % MOD) %= MOD;
	}
	
	return memo_g[x] = cnt;
}

int f(int x, int parent){
	if (memo_f[x] > 0) return memo_f[x];
	
	int white = g(x,parent);
	int black = 1;
	for(auto &&child: edge[x]){
		if (child == parent) continue;
		
		(black *= g(child, x) % MOD) %= MOD;
	}
	return memo_f[x] = (white + black) % MOD;	
}


signed main() {
	int n; cin >> n;
	for(int i=0;i<n-1;++i) {
		int fr,to; cin >> fr >> to;
		edge[fr-1].push_back(to-1);
		edge[to-1].push_back(fr-1);
	}
	
	int ans = f(0, -1);
	cout << ans << endl;
	
	return 0;
}

Submission Info

Submission Time
Task D - 塗り絵
User task4233
Language C++14 (Clang 3.8.0)
Score 100
Code Size 1009 Byte
Status AC
Exec Time 189 ms
Memory 7808 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 22
Set Name Test Cases
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt
Case Name Status Exec Time Memory
000.txt AC 3 ms 2560 KB
001.txt AC 3 ms 2560 KB
002.txt AC 149 ms 6656 KB
003.txt AC 189 ms 7808 KB
004.txt AC 120 ms 6016 KB
005.txt AC 185 ms 7808 KB
006.txt AC 168 ms 7424 KB
007.txt AC 188 ms 7808 KB
008.txt AC 130 ms 6272 KB
009.txt AC 186 ms 7808 KB
010.txt AC 134 ms 6400 KB
011.txt AC 188 ms 7808 KB
012.txt AC 109 ms 5760 KB
013.txt AC 187 ms 7808 KB
014.txt AC 85 ms 5120 KB
015.txt AC 186 ms 7808 KB
016.txt AC 112 ms 5888 KB
017.txt AC 184 ms 7808 KB
018.txt AC 33 ms 3584 KB
019.txt AC 187 ms 7808 KB
020.txt AC 18 ms 3072 KB
021.txt AC 186 ms 7808 KB