結果
| 問題 |
No.2214 Products on Tree
|
| ユーザー |
 vjudge1
|
| 提出日時 | 2025-10-09 16:48:53 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 207 ms / 3,000 ms |
| コード長 | 24,748 bytes |
| コンパイル時間 | 1,644 ms |
| コンパイル使用メモリ | 165,564 KB |
| 実行使用メモリ | 45,036 KB |
| 最終ジャッジ日時 | 2025-10-09 16:49:02 |
| 合計ジャッジ時間 | 8,320 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define multiple_cases(T) signed T; cin >> T; while (T--)
#define variable_name(x) #x
#define all(x) (x).begin(), (x).end()
#define adebug(a, b, c) #a << "[" << (b) << "..." << (c) << "] = " << vector<typename decay<decltype(*((a) + (b)))>::type>((a) + (b), (a) + (c) + 1)
#define file_io(a) (freopen(#a ".in", "r", stdin), freopen(#a ".out", "w", stdout))
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
const int mod = 998244353;
template<typename T, typename Tb>
T quickpower(T a, Tb b) {
if (b < 0) b = b % (mod - 1) + mod - 1;
T c = 1;
while (b) {
if (b & 1) {
c *= a;
c %= mod;
}
a *= a;
a %= mod;
b >>= 1;
}
return c;
}
template<typename T, typename Tb>
T auto_quickpower(T a, Tb b) {
T c = 1;
while (b) {
if (b & 1) {
c *= a;
}
a *= a;
b >>= 1;
}
return c;
}
namespace quick_io {
template<typename T>
ostream &operator<<(ostream &A, const vector<T> &b);
template<typename T>
ostream &operator<<(ostream &A, const deque<T> &b);
template<typename T1, typename T2>
ostream &operator<<(ostream &A, const pair<T1, T2> &b);
template<typename T>
ostream &operator<<(ostream &A, const set<T> &b);
template<typename T>
ostream &operator<<(ostream &A, const multiset<T> &b);
template<typename T, typename T2>
ostream &operator<<(ostream &A, const map<T, T2> &b);
template<typename T, typename T2>
ostream &operator<<(ostream &A, const multimap<T, T2> &b);
template<typename T>
ostream &operator<<(ostream &A, const unordered_set<T> &b);
template<typename T>
ostream &operator<<(ostream &A, const unordered_multiset<T> &b);
template<typename T, typename T2>
ostream &operator<<(ostream &A, const unordered_map<T, T2> &b);
template<typename T, typename T2>
ostream &operator<<(ostream &A, const unordered_multimap<T, T2> &b);
template<typename T>
ostream &operator<<(ostream &A, const vector<T> &b) {
A << "[";
for (size_t i = 0; i + 1 < b.size(); i++) {
A << b[i] << ",";
}
if (b.size()) {
A << b[b.size() - 1];
}
A << "]";
return A;
}
template<typename T>
ostream &operator<<(ostream &A, const deque<T> &b) {
A << "[";
for (size_t i = 0; i + 1 < b.size(); i++) {
A << b[i] << ",";
}
if (b.size()) {
A << b[b.size() - 1];
}
A << "]";
return A;
}
template<typename T1, typename T2>
ostream &operator<<(ostream &A, const pair<T1, T2> &b) {
return A << '(' << b.first << ',' << b.second << ')';
}
template<typename T>
ostream &operator<<(ostream &A, const set<T> &b) {
typename set<T>::const_iterator i = b.begin(), e = b.end();
A << "{";
while (i != e) {
A << *i;
i++;
if (i != e) {
A << ",";
}
}
return A << "}";
}
template<typename T>
ostream &operator<<(ostream &A, const multiset<T> &b) {
typename multiset<T>::const_iterator i = b.begin(), e = b.end();
A << "{";
while (i != e) {
A << *i;
i++;
if (i != e) {
A << ",";
}
}
return A << "}";
}
template<typename T, typename T2>
ostream &operator<<(ostream &A, const map<T, T2> &b) {
typename map<T, T2>::const_iterator i = b.begin(), e = b.end();
A << "{";
while (i != e) {
A << *i;
i++;
if (i != e) {
A << ",";
}
}
return A << "}";
}
template<typename T, typename T2>
ostream &operator<<(ostream &A, const multimap<T, T2> &b) {
typename multimap<T, T2>::const_iterator i = b.begin(), e = b.end();
A << "{";
while (i != e) {
A << *i;
i++;
if (i != e) {
A << ",";
}
}
return A << "}";
}
template<typename T>
ostream &operator<<(ostream &A, const unordered_set<T> &b) {
typename unordered_set<T>::const_iterator i = b.begin(), e = b.end();
A << "{";
while (i != e) {
A << *i;
i++;
if (i != e) {
A << ",";
}
}
return A << "}";
}
template<typename T>
ostream &operator<<(ostream &A, const unordered_multiset<T> &b) {
typename unordered_multiset<T>::const_iterator i = b.begin(), e = b.end();
A << "{";
while (i != e) {
A << *i;
i++;
if (i != e) {
A << ",";
}
}
return A << "}";
}
template<typename T, typename T2>
ostream &operator<<(ostream &A, const unordered_multimap<T, T2> &b) {
typename unordered_multimap<T, T2>::const_iterator i = b.begin(), e = b.end();
A << "{";
while (i != e) {
A << *i;
i++;
if (i != e) {
A << ",";
}
}
return A << "}";
}
template<typename T, typename T2>
ostream &operator<<(ostream &A, const unordered_map<T, T2> &b) {
typename unordered_map<T, T2>::const_iterator i = b.begin(), e = b.end();
A << "{";
while (i != e) {
A << *i;
i++;
if (i != e) {
A << ",";
}
}
return A << "}";
}
template<typename T1, typename T2>
istream &operator>>(istream &A, pair<T1, T2> &b) {
return A >> b.first >> b.second;
}
template<typename T>
void print_array(T b, T e, string s = " ") {
while (b != e) {
cout << *b;
b++;
if (b != e) {
cout << s;
}
}
}
template<typename T>
void auto_print(T &b, size_t n, string s = " ") {
for (size_t i = 1; i < n; i++) {
cout << b[i] << s;
}
cout << b[n];
}
template<typename T>
void auto_print(T &b, string s = " ") {
for (auto i : b) {
cout << i << s;
}
}
template<typename T>
void print_n(T b, size_t n, string s = " ") {
if (n == 0) return;
cout << *b;
for (size_t i = 1; i < n; i++) {
b++;
cout << s << *b;
}
}
template<typename T>
void read_array(T b, T e) {
while (b != e) {
cin >> *b;
b++;
}
}
template<typename T>
void auto_read(T &b, size_t n) {
for (size_t i = 1; i <= n; i++) {
cin >> b[i];
}
}
template<typename T>
void read_n(T b, size_t n) { // untested
cin >> *b;
for (size_t i = 1; i < n; i++) {
b++;
cin >> *b;
}
}
template <typename T>
std::string to_string(const T& value) {
std::ostringstream oss;
oss << value;
return oss.str();
}
std::string debug_index() {
return "";
}
template <typename first_t, typename... rest_t>
std::string debug_index(const first_t& first, const rest_t&... rest) {
return "[" + to_string(first) + "]" + debug_index(rest...);
}
template <typename T>
auto get_value(T&& arr) -> decltype(std::forward<T>(arr)) {
return std::forward<T>(arr);
}
template <typename T, typename first_t, typename... rest_t>
auto get_value(T&& arr, first_t&& first, rest_t&&... rest) {
return get_value(
std::forward<T>(arr)[std::forward<first_t>(first)],
std::forward<rest_t>(rest)...
);
}
#define debug(first, ...) #first << debug_index(__VA_ARGS__) << " = " << get_value(first, ##__VA_ARGS__)
#define spc << ' ' <<
#undef quick_io_int_length_limit
#undef quick_io_int_radix_type
#undef quick_io_length_type
}
namespace MATH {
template<typename Ta, typename Tb, typename Tm>
Ta quickpower(Ta a, Tb b, Tm MOD) { // MOD \in P
if (b < 0) {
b = b % (MOD - 1) + MOD - 1;
}
a %= MOD;
Ta c = 1;
while (b) {
if (b & 1) {
c *= a;
c %= MOD;
}
a *= a;
a %= MOD;
b >>= 1;
}
return c;
}
template<typename T>
T gcd(T a, T b) {
if (b == T(0))
return a;
return gcd(b, a % b);
}
template<typename T>
T lcm(T a, T b) {
return a * b / gcd(a, b);
}
template<typename T, typename T1, typename T2>
T exgcd(T a, T b, T1 &x, T2 &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
T ans = exgcd(b, a % b, x, y);
T1 X = y;
T2 Y = (T2)x - ((T2)a / (T2)b) * y;
x = X;
y = Y;
return ans;
}
template<typename T>
T log2_(T k) {
if (k == 0) return 0;
T ans = 0;
if (k >> 32) ans += 32, k >>= 32;
if (k >> 16) ans += 16, k >>= 16;
if (k >> 8) ans += 8, k >>= 8;
if (k >> 4) ans += 4, k >>= 4;
if (k >> 2) ans += 2, k >>= 2;
if (k >> 1) ans += 1;
return ans;
}
template<typename T, typename T2>
void build_power(T *power_array, T2 power_base, size_t len) {
power_array[0] = 1;
for (size_t i = 1; i <= len; i++) {
power_array[i] = power_array[i - 1] * (T)power_base;
}
}
template<typename T1, typename T2>
void build_factorial(int n, T1 *f, T2 *inv) {
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1] * (T1)i;
}
if (inv == nullptr) {
return;
}
inv[n] = T2(1) / T2(f[n]);
for (int i = n - 1; i >= 0; i--) {
inv[i] = inv[i + 1] * (T2)(i + 1);
}
}
template<typename T1, typename T2>
T1 C(size_t n, size_t m, T1 *f, T2 *i) {
if (m > n) return 0;
return f[n] * (T1)i[m] * (T1)i[n - m];
}
}
namespace modulo_int {
#define mint_int long long
void exgcd(mint_int& x, mint_int& y, mint_int n, mint_int m) {
if (m) {
exgcd(y, x, m, n % m);
y -= n / m * x;
} else {
x = 1;
y = 0;
}
}
mint_int mint_exgcd_a, mint_exgcd_b;
#define mint_mod mod
struct mint {
mint_int n;
mint() : n(0) {}
mint(const mint_int &_n) { n = (_n % mint_mod + mint_mod) % mint_mod; }
template<typename T> const mint operator+(const T &x) const { return n + mint(x).n; }
template<typename T> const mint operator-(const T &x) const { return n - mint(x).n; }
template<typename T> const mint operator*(const T &x) const { return n * mint(x).n; }
template<typename T> const mint operator%(const T &x) const { return n % mint(x).n; }
template<typename T> const mint operator|(const T &x) const { return n | mint(x).n; }
template<typename T> const mint operator&(const T &x) const { return n & mint(x).n; }
template<typename T> const mint operator^(const T &x) const { return n ^ mint(x).n; }
template<typename T> const mint operator/(const T &x) const {
exgcd(mint_exgcd_a, mint_exgcd_b, mint(x).n, mint_mod);
return n * mint_exgcd_a;
}
template<typename T> mint &operator+=(const T x) { return *this = *this + (mint)x; }
template<typename T> mint &operator-=(const T x) { return *this = *this - (mint)x; }
template<typename T> mint &operator*=(const T x) { return *this = *this * (mint)x; }
template<typename T> mint &operator/=(const T x) { return *this = *this / (mint)x; }
template<typename T> mint &operator%=(const T x) { return *this = *this % (mint)x; }
template<typename T> mint &operator|=(const T x) { return *this = *this | (mint)x; }
template<typename T> mint &operator&=(const T x) { return *this = *this & (mint)x; }
template<typename T> mint &operator^=(const T x) { return *this = *this ^ (mint)x; }
mint &operator++() { return *this = n + 1; }
mint &operator--() { return *this = n - 1; }
mint operator++(signed) {
n = ((n + 1 == mint_mod) ? 0 : (n + 1));
return n - 1;
}
mint operator--(signed) {
n = (n ? (n - 1) : (mint_mod - 1));
return n + 1;
}
template<typename T> bool operator<(const T &b) { return n < mint(b).n; }
template<typename T> bool operator<=(const T &b) { return n <= mint(b).n; }
template<typename T> bool operator>(const T &b) { return n > mint(b).n; }
template<typename T> bool operator>=(const T &b) { return n >= mint(b).n; }
template<typename T> bool operator==(const T &b) { return n == mint(b).n; }
template<typename T> bool operator!=(const T &b) { return n != mint(b).n; }
operator mint_int() const { return n; }
mint operator-() const { return -n; }
const mint &operator+() const { return *this; }
};
istream &operator>>(istream &A, mint &b) {
mint_int c;
A >> c;
b = c;
return A;
}
ostream &operator<<(ostream &A, const mint &b) {
return A << b.n;
}
#undef mint_mod
#undef mint_int
}
namespace fast_ios {
// #define fast_ios_buffer_enough
// #define fast_is_buffer_enough
// #define fast_os_buffer_enough
// #define fast_ios_jump_invisible
// #define fast_is_jump_invisible
// #define fast_os_jump_invisible
#ifdef fast_ios_buffer_enough
#define fast_is_buffer_enough
#define fast_os_buffer_enough
#endif
#ifdef fast_ios_jump_invisible
#define fast_is_jump_invisible
#define fast_os_jump_invisible
#endif
template<size_t buffer_size = 65536>
struct fast_reader_t {
// short, int, long, long long, __int128
// unsigned short, int, long, long long, __int128
// very safe if there are no overflow
size_t cursor;
unsigned char c;
unsigned char buffer[buffer_size];
inline fast_reader_t() : cursor(buffer_size), c(EOF) {}
inline unsigned char &get() {
#ifndef fast_is_buffer_enough
if (cursor < buffer_size) {
#endif
return c = buffer[cursor++];
#ifndef fast_is_buffer_enough
}
for (size_t i = fread(buffer, 1, buffer_size, stdin); i < buffer_size; i++) {
buffer[i] = EOF;
}
return c = buffer[(cursor = 0)++];
#endif
}
inline void unget() {
cursor--;
}
template<typename T>
typename enable_if<is_integral<T>::value && is_unsigned<T>::value, fast_reader_t&>::type
inline operator>>(T &x) {
x = 0;
while (get() < '0' || c > '9');
do {
x = (x << 3) + (x << 1) + (c ^ '0');
} while (get() >= '0' && c <= '9');
#ifndef fast_is_jump_invisible
unget();
#endif
return *this;
}
template<typename T>
typename enable_if<is_integral<T>::value && is_signed<T>::value, fast_reader_t&>::type
inline operator>>(T &x) {
typename make_unsigned<T>::type x_ = 0;
bool sign = false;
while ((get() < '0' || c > '9') && c != '-' && c != '+');
if (c == '-') {
sign = true;
get();
} else if (c == '+') {
get();
}
do {
x_ = (x_ << 3) + (x_ << 1) + (c ^ '0');
} while (get() >= '0' && c <= '9');
x = x_;
if (sign) {
x = -x;
}
#ifndef fast_is_jump_invisible
unget();
#endif
return *this;
}
inline fast_reader_t &operator>>(string &x) {
x = "";
while (get() <= 32);
do {
x += c;
} while (get() > 32);
#ifndef fast_is_jump_invisible
unget();
#endif
return *this;
}
inline fast_reader_t &operator>>(char *x) {
while (get() <= 32);
do {
*(x++) = c;
} while (get() > 32);
*x = 0;
#ifndef fast_is_jump_invisible
unget();
#endif
return *this;
}
template<typename T>
typename enable_if<is_floating_point<T>::value, fast_reader_t&>::type
inline operator>>(T &x) {
x = 0;
bool sign = false;
while ((get() < '0' || c > '9') && c != '-' && c != '+' && c != '.');
if (c == '-') {
sign = true;
get();
} else if (c == '+') {
get();
} else if (c == '.') {
unget();
}
if (c != '.') do {
x = x * 10 + (c ^ '0');
} while (get() >= '0' && c <= '9');
if (c == '.') {
T f = 0.1;
while (get() >= '0' && c <= '9') {
x += (c ^ '0') * f;
f /= 10;
}
}
if (sign) {
x = -x;
}
unget();
return *this;
}
};
template<size_t buffer_size = 65536>
struct fast_writer_t {
// short, int, long, long long, __int128
// unsigned short, int, long, long long, __int128
size_t cursor;
unsigned char buffer[buffer_size];
inline fast_writer_t() : cursor(0) {}
inline ~fast_writer_t() {
if (cursor) {
flush();
}
}
inline void flush() {
__builtin_fwrite(buffer, 1, cursor, stdout);
cursor = 0;
}
inline void put(unsigned char c) {
buffer[cursor++] = c;
#ifndef fast_os_buffer_enough
if (cursor == buffer_size) {
flush();
}
#endif
}
template<typename T>
typename enable_if<is_integral<T>::value
&& is_unsigned<T>::value
&& !is_same<unsigned char, T>::value,
fast_writer_t&>::type
inline operator<<(const T &x) {
if (x >= T(10)) {
*this << x / T(10);
}
put('0' ^ x % T(10));
return *this;
}
template<typename T>
typename enable_if<is_integral<T>::value
&& is_signed<T>::value
&& !is_same<char, T>::value,
fast_writer_t&>::type
inline operator<<(const T &x) {
if (x >= T(0)) {
return *this << (typename make_unsigned<T>::type)x;
} else {
put('-');
return *this << (typename make_unsigned<T>::type)(-x);
}
}
inline fast_writer_t &operator<<(char x) {
put(x);
return *this;
}
inline fast_writer_t &operator<<(unsigned char x) {
put(x);
return *this;
}
inline fast_writer_t &operator<<(const string &x) {
for (string::const_iterator it = x.cbegin(); it != x.cend(); it++) {
put(*it);
}
return *this;
}
inline fast_writer_t &operator<<(const char *x) {
while (*x) {
put(*(x++));
}
return *this;
}
inline fast_writer_t &operator<<(const unsigned char *x) {
while (*x) {
put(*(x++));
}
return *this;
}
};
fast_reader_t<> ewin;
fast_writer_t<> ewout;
}
template<typename T_key,
typename T_value,
typename head_container = vector<size_t>,
typename nxt_container = vector<size_t>,
typename data_container = vector<T_value>,
typename index_type = size_t>
struct basic_fs {
// front star, without initialization
data_container data;
nxt_container nxt;
head_container head;
index_type cnt;
basic_fs() : cnt(0) {}
struct data_t {
T_key key;
basic_fs* base;
struct iterator {
index_type pos;
data_t* base;
T_value &operator*() { return base->base->data[pos]; }
iterator &operator++() { pos = base->base->nxt[pos]; return *this; }
operator index_type&() { return pos; }
};
iterator end() { return {0, this}; }
iterator begin() { return {base->head[key], this}; }
void push_back(const T_value &value) {
base->data[++base->cnt] = value;
base->nxt[base->cnt] = base->head[key];
base->head[key] = base->cnt;
}
bool empty() { return base->head[key] == 0; }
size_t size() {
size_t ans = 0;
for (size_t i = base->head[key]; i; i = base->nxt[i]) {
ans++;
}
return ans;
}
void clear() { base->head[key] = 0; }
friend ostream &operator<<(ostream &os, const data_t &a) {
os << "[";
size_t i = a.base->head[a.key];
while (i) {
os << a.base->data[i];
i = a.base->nxt[i];
if (i) {
os << ",";
}
}
return os << "]";
}
};
data_t operator[](const T_key &x) { return {x, this}; }
};
template<typename T,
size_t index_range,
size_t value_size = index_range>
using array_fs = basic_fs<size_t,
T,
int[index_range],
int[value_size],
T[value_size],
int>;
namespace graph_algorithm {
// directivity "d"/"u", weightiness "w"/"u"
template<typename T>
void read_graph_d_u(T &&e, int m) {
int u, v;
while (m--) {
cin >> u >> v;
e[u].push_back(v);
}
}
template<typename T>
void read_graph_d_w(T &&e, int m) {
int u, v, w;
while (m--) {
cin >> u >> v >> w;
e[u].push_back({v, w});
}
}
template<typename T>
void read_graph_u_u(T &&e, int m) {
int u, v;
while (m--) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
}
template<typename T, typename T2>
void read_graph_u_w(T &&e, int m) {
int u, v, w;
while (m--) {
cin >> u >> v >> w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
}
}
#define lowbit(x) ((x)&-(x))
template<typename T, typename BIT_index = size_t, typename container = vector<BIT_index> >
struct BIT {
container t;
BIT() {}
BIT(const BIT_index &n) : t(n, 0) {}
BIT(T *a, const size_t &n) : t(a, next(a, n)) {
for (BIT_index i = 1; i < n; i++) {
if (i + lowbit(i) < n) {
t[i + lowbit(i)] += t[i];
}
}
}
template<typename ite>
BIT(const ite &b, const ite &e) : t(b, e) {
BIT_index n = t.size();
for (BIT_index i = 1; i < n; i++) {
if (i + lowbit(i) < n) {
t[i + lowbit(i)] += t[i];
}
}
}
BIT(const BIT_index &n, const T &a) : t(n, a) {
for (BIT_index i = 1; i < n; i++) {
if (i + lowbit(i) < n) {
t[i + lowbit(i)] += t[i];
}
}
}
void clear(const BIT_index &len = 0) {
t = container(len, 0);
}
size_t size() {
return t.size();
}
void update(BIT_index x, const T k) {
if (x == 0) {
t[0] += k;
}
#ifndef BIT_limit
#define __BIT_hd_limit(x) (x < t.size())
#else
#define __BIT_hd_limit(x) (BIT_limit(x))
#endif
while (x != 0 && __BIT_hd_limit(x)) {
t[x] += k;
x += lowbit(x);
}
#undef __BIT_hd_limit
}
T query(BIT_index x) {
T ans = t[0];
while (x) {
ans += t[x];
x ^= lowbit(x);
}
return ans;
}
T query(const BIT_index l, const BIT_index r) {
return query(r) - (l ? query(l - 1) : T(0));
}
T operator[](const BIT_index b) {
return query(b, b);
}
void resize(const BIT_index n) {
BIT_index m = t.size();
if (n <= t.size()) {
t.erase(t.begin() + n, t.end());
return;
}
t.insert(t.end(), n - m, 0);
for (BIT_index i = 0; i < n; i++) {
if (i + lowbit(i) >= m && i + lowbit(i) < n) {
t[i + lowbit(i)] += t[i];
}
}
}
};
#undef lowbit
template<typename T>
typename decay<decltype(*declval<T>())>::type range_sum(T a, const T &b) {
if (a == b) return *T();
typename decay<decltype(*declval<T>())>::type ans = *(a++);
while (a != b) {
ans += *(a++);
}
return ans;
}
template<typename T>
typename decay<decltype(*declval<T>())>::type range_prod(T a, const T &b) {
if (a == b) return *T();
typename decay<decltype(*declval<T>())>::type ans = *(a++);
while (a != b) {
ans *= *(a++);
}
return ans;
}
template<typename T>
typename decay<decltype(*declval<T>())>::type range_bor(T a, const T &b) {
if (a == b) return *T();
typename decay<decltype(*declval<T>())>::type ans = *(a++);
while (a != b) {
ans |= *(a++);
}
return ans;
}
template<typename T>
typename decay<decltype(*declval<T>())>::type range_band(T a, const T &b) {
if (a == b) return *T();
typename decay<decltype(*declval<T>())>::type ans = *(a++);
while (a != b) {
ans |= *(a++);
}
return ans;
}
template<typename T>
typename decay<decltype(*declval<T>())>::type range_bxor(T a, const T &b) {
if (a == b) return *T();
typename decay<decltype(*declval<T>())>::type ans = *(a++);
while (a != b) {
ans |= *(a++);
}
return ans;
}
template<typename T, typename T2>
void range_plus(T a, const T &b, const T2 &c) { while (a != b) { *a += c; a++; } }
template<typename T, typename T2>
void range_minus(T a, const T &b, const T2 &c) { while (a != b) { *a -= c; a++; } }
template<typename T, typename T2>
void range_multiplies(T a, const T &b, const T2 &c) { while (a != b) { *a *= c; a++; } }
template<typename T, typename T2>
void range_divides(T a, const T &b, const T2 &c) { while (a != b) { *a /= c; a++; } }
template<typename T, typename T2>
void range_negate(T a, const T &b) { while (a != b) { *a = -*a; a++; } }
template<typename T, typename T2>
void range_band(T a, const T &b, const T2 &c) { while (a != b) { *a &= c; a++; } }
template<typename T, typename T2>
void range_bor(T a, const T &b, const T2 &c) { while (a != b) { *a |= c; a++; } }
template<typename T, typename T2>
void range_bxor(T a, const T &b, const T2 &c) { while (a != b) { *a ^= c; a++; } }
template<typename T, typename T2>
void range_bnot(T a, const T &b) { while (a != b) { *a = ~*a; a++; } }
template<typename T1, typename T2>
typename decay<typename common_type<T1, T2>::type>::type std_max(const T1 &a, const T2 &b) { return a > b ? a : b; }
template<typename T1, typename T2>
typename decay<typename common_type<T1, T2>::type>::type std_min(const T1 &a, const T2 &b) { return a < b ? a : b; }
template<typename T>
void std_swap(T &x, T &y) { swap(x, y); }
template<typename T1, typename T2>
T1 &ckmin(T1 &a, const T2 &b) { if (b < a) { a = b; } return a; }
template<typename T1, typename T2>
T1 &ckmax(T1 &a, const T2 &b) { if (b > a) { a = b; } return a; }
template<typename T> // const reference to reference
T &crtr(const T& x) { return (T&)x; }
void sios() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
using namespace quick_io;
#define int long long
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>(y))?(x):(y))
#define lowbit(x) ((x)&-(x))
#define abs(x) (((x)<(0))?(-(x)):(x))
#define swap(a,b) a^=b^=a^=b
#define INF 1e18
#define sos ostream
#define sis istream
#define soss ostringstream
#define siss istringstream
#define bin(a,b) bitset<a>(b)
#define getbit(a,b) (((a)>>(b))&1)
#if 1 // using using of types
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pii>;
#endif
ostream &cans(cout);
// #define cout cerr
using namespace MATH;
using modulo_int::mint;
using namespace graph_algorithm;
// using fast_ios::ewin;
// using fast_ios::ewout;
// #define cin ewin
// #define cout ewout
int n;
mint dp[1000005][2];
array_fs<int, 1000005> e;
void dfs(int id, int fa)
{
dp[id][0] = 1;
dp[id][1] = 1;
for (int i : e[id])
{
if (fa != i)
{
dfs(i, id);
dp[id][1] = dp[id][1] * (dp[i][0] + dp[i][1]) + dp[id][0] * dp[i][1];
dp[id][0] = dp[id][0] * (dp[i][0] + dp[i][1]);
// cout << debug(dp, id, 0) << endl;
// cout << debug(dp, id, 1) << endl;
}
}
}
signed main() {
cin >> n;
read_graph_u_u(e, n - 1);
dfs(1, 0);
cout << dp[1][1];
return 0;
}