//後で解く #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define all(a) a.begin(),a.end() #define rep(i, n) for (ll i = 0; i < (n); i++) #define pb push_back #define debug(x) cerr << #x << ':' << x << '\n' #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair P; typedef complex com; constexpr int inf = 1000000010; constexpr ll INF = 1000000000000000010; constexpr ld eps = 1e-12; constexpr ld pi = 3.141592653589793238; template inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; } constexpr ll mod = 1000000007; ll half(ll n) { if (n & 1) n += mod; n >>= 1; return n; } void add(ll &a, ll b) { a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } constexpr int sz = 300010; vector> graph(sz, vector()); vector memox(sz, 1), memoy(sz, 1); void dfs1(int n, int p) { for (int i : graph[n]) { if (i == p) continue; dfs1(i, n); add(memox[n], half(memox[i])); } } void dfs2(int n, int p) { ll sum = 0; for (int i : graph[n]) { if (i == p) continue; add(memoy[i], half(memoy[n])); sum += half(memox[i]); } sum %= mod; for (int i : graph[n]) { if (i == p) continue; add(memoy[i], sum - half(memox[i])); dfs2(i, n); } } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int n; cin >> n; rep(i, n - 1) { int u, v; cin >> u >> v; u--; v--; graph[u].pb(v); graph[v].pb(u); } dfs1(0, -1); dfs2(0, -1); }