結果
| 問題 | No.3412 Christmas Tree Coloring |
| コンテスト | |
| ユーザー |
 yimiya（いみや）
|
| 提出日時 | 2026-01-23 15:36:55 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 147 ms / 2,000 ms |
| コード長 | 29,856 bytes |
| 記録 | |
| コンパイル時間 | 4,256 ms |
| コンパイル使用メモリ | 354,020 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2026-01-23 15:37:03 |
| 合計ジャッジ時間 | 7,892 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
# include <algorithm>
# include <bitset>
# include <complex>
# include <cmath>
#define _USE_MATH_DEFINES
#include <assert.h>
# include <math.h>
# include <deque>
# include <exception>
# include <fstream>
# include <functional>
# include <iomanip>
# include <ios>
# include <iosfwd>
# include <iostream>
# include <istream>
# include <iterator>
# include <limits>
# include <list>
# include <locale>
# include <map>
# include <memory>
# include <new>
# include <numeric>
# include <ostream>
# include <queue>
# include <set>
# include <sstream>
# include <stack>
# include <stdexcept>
# include <streambuf>
# include <string>
# include <typeinfo>
# include <utility>
# include <valarray>
# include <vector>
# include <array>
# include <atomic>
# include <chrono>
# include <condition_variable>
# include <forward_list>
# include <future>
# include <initializer_list>
# include <mutex>
# include <random>
# include <ratio>
# include <regex>
# include <scoped_allocator>
# include <system_error>
# include <thread>
# include <tuple>
# include <typeindex>
# include <type_traits>
# include <unordered_map>
# include <unordered_set>
# include <bitset>
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
template<class S,class T>bool chmin(S&a,T b){if(a>b){a=b;return true;}return false;}
template<class S,class T>bool chmax(S&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>T Min(T a,T b){return a<b?a:b;}
template<class T,class...Args>T Min(T a,T b,Args...args){return Min(Min(a,b),args...);}
template<class T>T Max(T a,T b){return a>b?a:b;}
template<class T,class...Args>T Max(T a,T b,Args...args){return Max(Max(a,b),args...);}
#define rep(i,n) for (ll i = 0;i < (ll)(n);i++)
#define Yes cout << "Yes\n"// YESの短縮
#define No cout << "No\n"// NOの短縮
#define YN(x) cout<<((x)?"Yes":"No")<<'\n'
#define rtr0 return(0)//return(0)の短縮
#define gyakugen(x) modpow(x,mod - 2,mod);
#define agyakugen(x) modpow(x,amod - 2,amod);
#define st(A) sort((A).begin(),(A).end());
#define rst(A) sort((A).rbegin(),(A).rend());
#define rev(A) reverse((A).begin(),(A).end());
#define unq(A) (A).erase(unique((A).begin(),(A).end()),(A).end());
using namespace std;
//using namespace ranges;
using ll = long long;//63bit型整数型
using ld = long double;//doubleよりも長い値を保存できるもの
using ull = unsigned long long;//符号がない64bit型整数
template <class T>using maxpq = priority_queue<T>;
template <class T>using minpq = priority_queue<T,vector<T>,greater<T>>;
//ld m_pi = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679;
ll mod = 998244353;
ll amod = 1000000007;
ll MINF = -5000000000000000000;
ll INF = 5e18;
ll inf = 2000000000;
ll minf = -2000000000;
ll BAD = -1;
ll zero = 0;
ld EPS = 1e-10;
vector<ll>randomhash = {(ll)1e9 + 7,(ll)1e9 + 801,((ll)1e8 * 8) + 29,((ll)1e8 * 7) + 159,((ll)1e8 * 9) + 221};
vector<ll>tate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック
vector<ll>yoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック
vector<ll>etate = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック
vector<ll>eyoko = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック
vector<ll>hexsax = {0,1,1,0,-1,-1};
vector<ll>hexsay = {1,1,0,-1,-1,0};
//返り値は素数のリスト。
vector < bool > isprime;
vector < ll > Era(int n){//書き方 vector<ll>[] = Era(x); とやるとxまでの素数が出てくる。
isprime.resize(n, true);
vector < ll > res;
isprime[0] = false;
isprime[1] = false;
for(ll i = 2; i < n; ++i) isprime[i] = true;
for(ll i = 2; i < n; ++i) {
if(isprime[i]) {
res.push_back(i);
for(ll j = i * 2; j < n; j += i) isprime[j] = false;
}
}
return res;
}
ll ceil_div(ll a, ll b){
if (b <= 0) return INF; // invalid (分母<=0 のときは不可能と扱う)
return (a + b - 1) / b;
}
// 素数判定 21~35
ull modmul(ull a,ull b,ull mod) {
return (ull)a*b%mod;
}
ll modpow(ll a, ll n, ll mod) {
ll res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
long long npow(long long a, long long n){
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a;
a = a * a;
n >>= 1;
}
return res;
}
// モッドを使った累乗
long long isqrt(long long num){
return((long long)sqrtl(num));
}
ld get_theta(ld px,ld py,ld fx,ld fy,ld sx,ld sy){
ld fxv = fx-px;
ld fyv = fy-py;
ld sxv = sx-px;
ld syv = sy-py;
ld fsv = fxv*sxv + fyv*syv;
ld pfs = (ld)sqrt(fxv*fxv+fyv*fyv);
ld pss = (ld)sqrt(sxv*sxv+syv*syv);
return acos(fsv/(pfs*pss))*180/M_PI;
};
ld Euclidean_distance(ll x1,ll y1,ll x2,ll y2){
ld x = abs((ld)x1 - (ld)x2);
ld y = abs((ld)y1 - (ld)y2);
return sqrt((x*x) + (y*y));
};
ll Manhattan_distance(ll x1,ll y1,ll x2,ll y2){
return abs(x1-x2)+abs(y1-y2);
};
void change_bit(ll N,ll end,vector<ll>&X){
for(int i = 0;i<end;i++){
if((1<<i)&N)X[i] = 1;
else X[i] = 0;
}
}
ll popcount(ll x) {
int count = 0;
while (x) {
count += x & 1;
x >>= 1;
}
return count;
}
ll cutup(ll a,ll b){
return (a-1)/b + 1;
}
void Run_Length_Encoding(vector<ll>A,vector<pair<ll,ll>>&RLE){
RLE.push_back({A[0],1});
ll N = A.size();
for(int i = 1;i<N;i++){
if(RLE[RLE.size()-1].first==A[i])RLE[RLE.size()-1].second++;
else RLE.push_back({A[i],1});
}
}
bool is_in_grid(ll i,ll ii,ll H,ll W){
bool res = false;
if(i>=0&&i<H&&ii>=0&&ii<W)res=true;
return res;
}
template<long long MOD>
class ModInt {
private:
long long val;
// 拡張ユークリッドの互除法で逆元を計算
static long long mod_pow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
// フェルマーの小定理を使った逆元計算（MODが素数の場合）
static long long mod_inv(long long a, long long mod) {
return mod_pow(a, mod - 2, mod);
}
public:
// コンストラクタ
ModInt() : val(0) {}
ModInt(long long x) : val(((x % MOD) + MOD) % MOD) {}
// 値の取得
long long value() const { return val; }
// 四則演算の演算子オーバーロード
ModInt operator+(const ModInt& other) const {
return ModInt((val + other.val) % MOD);
}
ModInt operator-(const ModInt& other) const {
return ModInt((val - other.val + MOD) % MOD);
}
ModInt operator*(const ModInt& other) const {
return ModInt((val * other.val) % MOD);
}
ModInt operator/(const ModInt& other) const {
assert(other.val != 0); // 0除算チェック
return ModInt((val * mod_inv(other.val, MOD)) % MOD);
}
// 代入演算子
ModInt& operator+=(const ModInt& other) {
val = (val + other.val) % MOD;
return *this;
}
ModInt& operator-=(const ModInt& other) {
val = (val - other.val + MOD) % MOD;
return *this;
}
ModInt& operator*=(const ModInt& other) {
val = (val * other.val) % MOD;
return *this;
}
ModInt& operator/=(const ModInt& other) {
assert(other.val != 0); // 0除算チェック
val = (val * mod_inv(other.val, MOD)) % MOD;
return *this;
}
// 比較演算子
bool operator==(const ModInt& other) const {
return val == other.val;
}
bool operator!=(const ModInt& other) const {
return val != other.val;
}
// 単項演算子
ModInt operator+() const {
return *this;
}
ModInt operator-() const {
return ModInt(val == 0 ? 0 : MOD - val);
}
// べき乗
ModInt pow(long long exp) const {
return ModInt(mod_pow(val, exp, MOD));
}
// 出力用
friend std::ostream& operator<<(std::ostream& os, const ModInt& m) {
return os << m.val;
}
// 入力用
friend std::istream& operator>>(std::istream& is, ModInt& m) {
long long x;
is >> x;
m = ModInt(x);
return is;
}
};
//roli
template<class T>
struct rolling_hash{
vector<ull>Power,hash,InvPower;
ll B = 0;
ll MOD = 0;
void set_number(ll base,ll mod){
B = base;
MOD = mod;
}
void do_hash(const T &S) {
ll N = S.size();
Power.resize(N+1);
InvPower.resize(N+1);
hash.resize(N+1);
Power[0] = 1;
InvPower[0] = 1;
for (ll i = 0;i<N;i++) {
Power[i + 1] = modmul(Power[i],B,MOD);
InvPower[i + 1] = modpow(Power[i+1],MOD-2,MOD);
hash[i + 1] = (hash[i] + modmul(S[i], Power[i],MOD))%MOD;
}
}
ll get_hash(ll l, ll r) {
ull res = (hash[r]+MOD-hash[l])%MOD;
res = modmul(res,InvPower[l],MOD);
return res;
}
};
//flo
template<class T>
struct Floyd_Warshall{
public:
vector<vector<T>>ans;
ll N;
void reset(T n){
N = n;
ans.assign(N,vector<ll>(N,INF));
for(int i = 0;i<N;i++)ans[i][i]=0;
}
void indirected_set(T u,T v,T cost){
ans[u][v] = cost;
ans[v][u] = cost;
}
void directed_set(T u,T v,T cost){
ans[u][v] = cost;
}
void do_Floyd_Warshall(){
for(int ii = 0;ii<N;ii++){
for(int i = 0;i<N;i++){
for(int i3 = 0;i3<N;i3++){
if(ans[i][ii]==INF||ans[ii][i3]==INF)continue;
if(ans[i][i3]>ans[i][ii]+ans[ii][i3])ans[i][i3] = ans[i][ii]+ans[ii][i3];
}
}
}
}
T get(T u,T v){
return ans[u][v];
}
};
//comb
template<class T>
struct combination{
public:
vector<T>factorial;
ll MOD;
ll N;
void reset(T n,T mod){
N = n+1;
factorial.assign(N,1);
MOD = mod;
}
void calu(){
for(ll i = 1;i<N;i++){
factorial[i] = (factorial[i-1]*(i))%MOD;
}
}
T get(T n, T r){
ll a = factorial[n];
ll b = (factorial[r]*(factorial[n-r]))%MOD;
b = modpow(b,MOD - 2,MOD);
return (a*b)%MOD;
}
};
//dik
template<class T>
struct dijkstra{
public:
vector<vector<pair<T,T>>>graph;
vector<T>ans;
priority_queue<pair<T,T>,vector<pair<T,T>>,greater<pair<T,T>>>pq;
void do_dijkstra(T start){//頂点xからダイクストラを行う
ans.assign(ans.size(), INF);
pq.push({0,start});
ans[start] = 0;
while(true){
if(pq.empty())break;
T cost = pq.top().first;
T vertex = pq.top().second;
cout << cost << " " << vertex << "\n";
pq.pop();
if (cost > ans[vertex]) continue;
for(T i = 0;i<graph[vertex].size();i++){
T nextvertex = graph[vertex][i].first;
T nextcost = graph[vertex][i].second + cost;
if(ans[nextvertex] <= nextcost)continue;
ans[nextvertex] = nextcost;
pq.push({nextcost,nextvertex});
}
}
}
void make_indirectedgraph(T u,T v,T cost){//無向辺のグラフ作成
graph[u].push_back({v,cost});
graph[v].push_back({u,cost});
}
void make_directedgraph(T u,T v,T cost){//有向辺のグラフ作成
graph[u].push_back({v,cost});
}
T output(T end){//答えを出す
return ans[end];
}
void reset(T N){//リセット
graph.assign(N, {});
ans.assign(N, INF);
}
};
//uf
template<class T>
struct unionfind {
public:
vector<T> parent, rank;
void reset(T N) { // 初期化
parent.resize(N);
rank.assign(N, 1); // 各集合のサイズを 1 にする
for (T i = 0; i < N; i++) parent[i] = i;
}
T leader(T x) { // 経路圧縮による親の取得
if (parent[x] == x) return x;
return parent[x] = leader(parent[x]); // 経路圧縮
}
void marge(T x, T y) { // ランクによるマージ
T a = leader(x), b = leader(y);
if(a!=b){
if (rank[a] < rank[b]) swap(a, b);
parent[b] = a;
rank[a] += rank[b]; // サイズを更新
}
}
bool same(T x, T y) { // 同じ集合か判定
return leader(x) == leader(y);
}
T size(T x) { // 集合のサイズを取得
return rank[leader(x)];
}
void check(T N) { // デバッグ用: 親の確認
for (T i = 0; i < N; i++) cout << parent[i] << " ";
cout << "\n";
}
};
//scc
struct SCC {
//kosaraju法を用いたSCC
int N;
// グラフ
vector<vector<int>> g, rg;
// Kosaraju 用
vector<int> comp, order;
vector<bool> used;
// 結果
int scc_count;
vector<vector<int>> groups; // 各 SCC に含まれる頂点
vector<vector<int>> dag; // 縮約 DAG
vector<int> sz; // SCC サイズ
vector<int> indeg, outdeg; // DAG の入出力次数
// --- コンストラクタ ---
SCC() : N(0) {}
SCC(int n) { reset(n); }
void reset(int n) {
N = n;
g.assign(N, {});
rg.assign(N, {});
}
void add_edge(int u, int v) {
g[u].push_back(v);
rg[v].push_back(u);
}
// --- 1回目 DFS（帰りがけ順） ---
//stackに積む行動
void dfs1(int v) {
used[v] = true;
for (int to : g[v]) {
if (!used[to]) dfs1(to);
}
order.push_back(v);
}
// --- 2回目 DFS（逆グラフ） ---
//stackに積んだものを集合に直す行動
void dfs2(int v, int c) {
comp[v] = c;
groups[c].push_back(v);
for (int to : rg[v]) {
if (comp[to] == -1) dfs2(to, c);
}
}
void do_scc() {
// 1st DFS
used.assign(N, false);
order.clear();
for (int i = 0; i < N; i++) {
if (!used[i]) dfs1(i);
}
// 2nd DFS
comp.assign(N, -1);
scc_count = 0;
groups.clear();
for (int i = N - 1; i >= 0; i--) {
int v = order[i];
if (comp[v] == -1) {
groups.push_back({});
dfs2(v, scc_count);
scc_count++;
}
}
// SCC サイズ
sz.assign(scc_count, 0);
for (int i = 0; i < scc_count; i++) {
sz[i] = (int)groups[i].size();
}
// 縮約 DAG 構築
dag.assign(scc_count, {});
indeg.assign(scc_count, 0);
outdeg.assign(scc_count, 0);
// 重複辺除去
set<pair<int,int>> seen;
for (int v = 0; v < N; v++) {
for (int to : g[v]) {
int a = comp[v];
int b = comp[to];
if (a != b && !seen.count({a, b})) {
seen.insert({a, b});
dag[a].push_back(b);
outdeg[a]++;
indeg[b]++;
}
}
}
}
};
//セグ木
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())){
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do{
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
}while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do{
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
}while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
};
//遅延セグ木
template <class S,S (*op)(S, S),S (*e)(),class F,S (*mapping)(F, S),F (*composition)(F, F),F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
//オイラーツアー
struct Euler_Tour{//最小共通祖先,部分木のコスト,通り道のコスト,のグラフを作る部分(オイラーツアー)
//必要なもの集
//セグ木は2*Nがベース
//LCA(最小共通祖先)discovery,finish,visit,high
//とある頂点xを根とする部分木の範囲 discovery,finish
//頂点xを根とする部分木の辺と頂点のコストの総和 discovery,finish,vcost1,ecost1
//頂点xを根とする頂点yまでの最短の辺と頂点のコストの総和 discovery,finish,vcost2,ecost2
vector<int>discovery,finish,visit,high,vweight,vcost1,vcost2,ecost1,ecost2;
vector<int>other;
vector<vector<pair<int,int>>>graph;
int cnt;
int othercnt;
void reset(ll N){
cnt = 0;
othercnt = 0;
other.assign(2*N,0);
discovery.assign(N,inf);
finish.assign(N,minf);
vweight.assign(N,0);
graph.assign(N,vector<pair<int,int>>(0));
visit.assign(2*N,0);
high.assign(2*N,0);
vcost1.assign(2*N,0);
vcost2.assign(2*N,0);
ecost1.assign(2*N,0);
ecost2.assign(2*N,0);
};
void make_graph(ll u,ll v,ll cost){
if(max(u,v)>graph.size()){
cerr << "Error: Vertex out of range. u=" << u << ", v=" << v << "\n";
return;
}
graph[u].push_back({v,cost});
graph[v].push_back({u,cost});
}
void set_vweight(ll vertex,ll cost){
vweight[vertex]+=cost;
}
void DFS(ll vertex,ll nowdepth,ll cost){
if(discovery[vertex]==inf){
vcost1[cnt]=vweight[vertex];
vcost2[cnt]=vweight[vertex];
}
else{
vcost1[cnt]=0;
vcost2[cnt]=0;
}
ecost1[cnt]=cost;
ecost2[cnt]=cost;
discovery[vertex]=min(discovery[vertex],cnt);
visit[cnt]=vertex;
high[cnt]=nowdepth;
for(int i = 0;i<graph[vertex].size();i++){
int x = graph[vertex][i].first;
int nextcost = graph[vertex][i].second;
if(discovery[x]!=inf&&graph[vertex].size()==1)othercnt++;
other[cnt]=othercnt;
if(discovery[x]==inf){
cnt++;
DFS(x,nowdepth+1,nextcost);
cnt++;
visit[cnt]=vertex;
high[cnt]=nowdepth;
vcost1[cnt]=0;
ecost1[cnt]=0;
vcost2[cnt]=vweight[x]*-1;
ecost2[cnt]=nextcost*-1;
}
other[cnt]=othercnt;
}
finish[vertex]=cnt+1;
return;
}
int get_size(){
ll res = high.size()-1;
return res;
}
int get_vcost1(ll i){
return ecost1[i];
}
int get_vcost2(ll i){
return vcost2[i];
}
int get_ecost1(ll i){
return vcost1[i];
}
int get_ecost2(ll i){
return ecost2[i];
}
int get_high(ll i){
return high[i];
}
int get_visit(ll i){
return visit[i];
}
int get_discovery(ll i){
return discovery[i];
}
int get_finish(ll i){
return finish[i];
}
};
//二次元グリッドの回転
template<typename T>
void rotate(vector<vector<T>>& ary,bool rev=false){
int n=ary.size(),m=ary[0].size();
vector copy(m,vector<T>(n));
rep(i,n)rep(j,m){
if(!rev)copy[j][n-i-1]=ary[i][j];
else copy[m-j-1][i]=ary[i][j];
}
ary=copy;
}
//セグ木のベース
/*
using segS = ll;
segS oop(segS a,segS b){
return (a+b)%mod;
}
segS ee(){
return 0;
}
/*
struct segS{
ll mi = 0;
ll ma = 0;
};
segS oop(segS a,segS b){
segS res;
res.mi = min(a.mi,b.mi);
res.ma = max(a.ma,b.ma);
return res;
}
segS ee(){
segS res;
res.mi = INF;
res.ma = MINF;
return res;
}
using lazyS = ll;
struct Date{
ll x,y;
};
struct Date2{
ll move,p;
};*/
//遅延セグ木のベース
/*using lazyS = ll;
using lazyF = ll;
lazyS e(){ return -1;}//範囲外などを起こしてしまったときの返り値
lazyS op(lazyS a, lazyS b){
lazyS c = max(a,b);
return c;
}//操作したいこと
lazyS mapping(lazyF f, lazyS x){
x = max(f,x);
return x;
}//下まで伝播させたいこと
lazyF composition(lazyF f, lazyF g){
g = max(f,g);
return g;
}//まとめてやった場合おこしたいこと
lazyF id(){ return -1; }//遅延セグ木のベース
*/
using mint = ModInt<998244353>;
using amint = ModInt<1000000007>;
void print_1D(vector<ll>&A,bool kaigyou){
ll N = A.size();
cout << "----------\n";
for(int i = 0;i<N;i++){
cout << A[i] << " ";
if(kaigyou)cout << "\n";
}
cout << "\n";
cout << "----------\n";
}
void print_2D(vector<vector<ll>>&A){
ll N = A.size();
cout << "----------\n";
for(int i = 0;i<N;i++){
for(int ii = 0;ii<A[i].size();ii++){
cout << A[i][ii] << " ";
}
cout << "\n";
}
cout << "----------\n";
}
vector<ll> prefix_1Dsum(vector<ll>&A){
ll N = A.size();
vector<ll>B(N+1);
for(int i = 0;i<N;i++){
B[i+1]+=A[i];
B[i+1]+=B[i];
}
return B;
}
vector<vector<ll>> prefix_2Dsum(vector<vector<ll>>&A){
ll N = A.size();
ll M = A[0].size();
vector<vector<ll>>B(N+1,vector<ll>(M+1));
for(int i = 0;i<N;i++){
for(int ii = 0;ii<M;ii++){
B[i+1][ii+1]+=A[i][ii];
B[i+1][ii+1]+=B[i+1][ii];
}
}
for(int ii = 0;ii<M;ii++){
for(int i = 0;i<N;i++){
B[i+1][ii+1]+=B[i][ii+1];
}
}
return B;
}
ll get_prefix_1Dsum(vector<ll>&A,ll l,ll r){//マイナスしないまま区間に突っ込む
if(l == 0||l>r)cout << "error" << "\n";
return A[r]-A[l-1];
}
ll get_prefix_2Dsum(vector<vector<ll>>&A,ll x1,ll y1,ll x2,ll y2){//マイナスしないまま区間に突っ込む
if(x1>x2||y1>y2)cout << "error" << "\n";
return A[x2][y2]-A[x1-1][y2]-A[x2][y1-1]+A[x1-1][y1-1];
}
int main(){
ll N;
cin >> N;
vector<ll>A(N);
for(int i = 0;i<N-1;i++){
ll a,b;
cin >> a >> b;
a--;
b--;
A[a]++;
A[b]++;
}
ll ans = 0;
rst(A);
bool ok = true;
for(int i = 1;i<N;i++){
if(A[i]!=1)ok = false;
}
if(ok){
for(int i = 0;i<N;i++){
if(i==0){
ans += modpow(2,A[i],mod);
ans = (ans-2+mod)%mod;
ans %= mod;
}
else{
ans += modpow(2,A[i],mod);
ans %= mod;
}
}
goto next;
}
for(int i = 0;i<N;i++){
ans += modpow(2,A[i],mod);
ans %= mod;
}
next:;
cout << ans << "\n";
}