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 |
|
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 |