MOD = 10**9 + 7
from collections import *
import sys
itr = (line for line in sys.stdin.read().split('\n'))
INP = lambda: next(itr)
def ni(): return int(INP())
def nl(): return [int(_) for _ in INP().split()]
def solve():
N = ni()
adj = [[] for _ in range(N)]
for i in range(N-1):
u, v = nl()
adj[u-1].append(v-1)
adj[v-1].append(u-1)
chs = [[] for _ in range(N)]
back = [[] for _ in range(N)]
q = [0]
vis = set(q)
while q:
q2 = []
for u in q:
for v in adj[u]:
if v in vis: continue
chs[u].append(v)
back[v].append(u)
q2.append(v)
vis.add(v)
q = q2
ps = [len(chs[u]) for u in range(N)]
D = [-1]*N
q = [u for u in range(N) if ps[u] == 0]
i = 0
order = []
while q:
q2 = []
for u in q:
order.append(u)
for v in back[u]:
ps[v] -= 1
if ps[v] == 0:
q2.append(v)
D[u] = i
q = q2
i += 1
pw = pow(2, N-1, MOD)
su = sum(d + 1 for d in D)
print(pw*su%MOD)
def main():
T = ni()
for _ in range(T):
solve()
if __name__ == '__main__':
main()
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <random>
using namespace std;
std::default_random_engine generator;
int rnd(int l, int r)
{
std::uniform_int_distribution<int> distribution(l, r);
return distribution(generator);
}
template<class T> inline T gcd(T a, T b)
{
if(a < 0) return gcd(-a, b);
if(b < 0) return gcd(a, -b);
return (b==0) ? a : gcd(b, a%b);
}
template<class T> inline T lcm(T a, T b)
{
return a / gcd(a, b) * b;
}
long long mod = 1000000007;
const double pi = 3.141592653589793238462643383279;
long long powmod(long long x, long long p)
{
if(p == 0)
return 1;
if(p&1)
return x * powmod(x*x%mod, p/2) % mod;
else
return powmod(x*x%mod, p/2) % mod;
}
long long factorial_mod(long long n)
{
long long res = 1;
for (long long i = 2; i <= n; ++i) {
res = (res * i) % mod;
}
return res;
}
long long intsqrt(long long x) {
long long sx = sqrt((double)x) + 1;
if (sx*sx <= x)
return sx;
else
return sx-1;
}
void dfs(int u, int p, vector<vector<int>> &g, vector<int> &depth)
{
for (int v : g[u]) {
if (v != p) {
dfs(v, u, g, depth);
}
}
for (int v : g[u]) {
if (v != p) {
depth[u] = max(depth[u], depth[v] + 1);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cout.precision(12);
cout << fixed;
cin.tie(0);
int numTestCases = 1;
cin >> numTestCases;
for(int Case = 1; Case <= numTestCases; ++Case)
{
int n;
cin >> n;
long long pow2 = 1;
for (int i = 0; i < n-1; ++i) {
pow2 = pow2 * 2 % mod;
}
vector<vector<int>> g(n);
for (int i = 0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> depth(n);
dfs(0, -1, g, depth);
long long res = 0;
for (int i = 0; i < n; ++i) {
res = (res + pow2 * (1+depth[i]) % mod) % mod;
}
cout << res;
cout << endl;
//cout << "Case #" << Case <<": ";
}
return 0;
}
1476E - Pattern Matching | 1107A - Digits Sequence Dividing |
1348A - Phoenix and Balance | 1343B - Balanced Array |
1186A - Vus the Cossack and a Contest | 1494A - ABC String |
1606A - AB Balance | 1658C - Shinju and the Lost Permutation |
1547C - Pair Programming | 550A - Two Substrings |
797B - Odd sum | 1093A - Dice Rolling |
1360B - Honest Coach | 1399C - Boats Competition |
1609C - Complex Market Analysis | 1657E - Star MST |
1143B - Nirvana | 1285A - Mezo Playing Zoma |
919B - Perfect Number | 894A - QAQ |
1551A - Polycarp and Coins | 313A - Ilya and Bank Account |
1469A - Regular Bracket Sequence | 919C - Seat Arrangements |
1634A - Reverse and Concatenate | 1619C - Wrong Addition |
1437A - Marketing Scheme | 1473B - String LCM |
1374A - Required Remainder | 1265E - Beautiful Mirrors |