Submission #3692096


Source Code Expand

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(10);

}

const ll V = 100000;
using P = pair<ll, ll>;
vector<ll> G[V];	//pair<辺の距離, 行き先の頂点>
vector<bool> used(V);
vector<ll> dpf, dpg;
ll calcg(ll num, ll par);

ll calcf(ll num, ll par) {
	if (dpf[num] != -1) {
		return dpf[num];
	}

	dpf[num] = calcg(num, par);

	ll tmp = 1;

	REP(i, G[num].size()) {
		if (G[num][i] == par) {
			continue;
		}
		tmp = tmp * calcg(G[num][i], num) % _MOD;
	}

	dpf[num] = (dpf[num] + tmp) % _MOD;

	return dpf[num];
}

ll calcg(ll num, ll par) {
	if (dpg[num] != -1) {
		return dpg[num];
	}

	dpg[num] = 1;

	REP(i, G[num].size()) {
		if (G[num][i] == par) {
			continue;
		}
		dpg[num] = dpg[num] * calcf(G[num][i], num) % _MOD;
	}

	return dpg[num];
}

signed main() {
	ll n, a, b;

	cin >> n;

	REP(i, n - 1) {
		cin >> a >> b;
		G[a - 1].push_back(b - 1);
		G[b - 1].push_back(a - 1);
		dpf.push_back(-1);
		dpg.push_back(-1);
	}

	dpf.push_back(-1);
	dpg.push_back(-1);

	cout << calcf(0, -1) << endl;
}

Submission Info

Submission Time
Task D - 塗り絵
User vjudge4
Language Bash (GNU bash v4.3.11)
Score 0
Code Size 1949 Byte
Status RE
Exec Time 297 ms
Memory 1912 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
RE × 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 RE 297 ms 1912 KB
001.txt RE 3 ms 504 KB
002.txt RE 3 ms 504 KB
003.txt RE 3 ms 504 KB
004.txt RE 3 ms 504 KB
005.txt RE 3 ms 504 KB
006.txt RE 3 ms 504 KB
007.txt RE 3 ms 504 KB
008.txt RE 3 ms 504 KB
009.txt RE 3 ms 504 KB
010.txt RE 3 ms 504 KB
011.txt RE 3 ms 504 KB
012.txt RE 3 ms 504 KB
013.txt RE 3 ms 504 KB
014.txt RE 3 ms 504 KB
015.txt RE 3 ms 504 KB
016.txt RE 3 ms 504 KB
017.txt RE 3 ms 504 KB
018.txt RE 3 ms 604 KB
019.txt RE 3 ms 504 KB
020.txt RE 3 ms 504 KB
021.txt RE 3 ms 504 KB