标题

题意

思路

代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<utility>
#include<string.h>
#include<ext/rope> 
#include<queue>
#include<stack>
using namespace std;
using namespace __gnu_cxx;
#define int  long long
#define dnt double
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define dow(i,j,k) for(i=(j);i>=(k);--i)
#define pr pair
#define mkp make_pair
#define fi first
#define se second
int gp() {int x;while((x=rand())<=0)srand(time(0));return x%1000;}
inline int read(int &x) {
   x=0;int ff=1;char ch=getchar();
   while (ch<'0'||ch>'9') {
   	if (ch=='-') ff=-1;ch=getchar();
   }
   while (ch>='0'&&ch<='9') {
   	x=x*10+ch-48;ch=getchar();
   }
   return x*ff;
}
void write(int x) {
 if (x > 9)write(x / 10);
 putchar((x % 10) + '0');
}
inline int max(int a,int b) {return a>b?a:b;}
inline int min(int a,int b) {return a>b?b:a;}
inline int exgcd(int a,int b,int&x,int&y) {
   if(b==0) {x=1,y=0 ;return a ;} 
   else {int r=exgcd(b,a%b,x,y);int t=x ;x=y ;y=t-a*y/b ;return r ;}
}

struct matrix {
   int n,m;
   int num[102][102];
   void pri() {
   	for(int i=1; i<=n; i++) {
   		for(int j=1; j<=m; j++) {
   			cout<<num[i][j]<<" ";
   		}
   		cout<<endl;
   	}
   }
   matrix operator*(matrix y) {
   	matrix x=*this;
   	matrix c;
   	c.n=x.n;
   	c.m=y.m;
   	memset(c.num,0,sizeof(c.num));
   	for(int i=1; i<=x.n; i++) {
   		for(int k=1; k<=x.m; k++){
   			if(x.num[i][k])
   			for(int j=1; j<=y.m; j++){
   			c.num[i][j]+=x.num[i][k]*y.num[k][j];
   			//	c.num[i][j]+=((x.num[i][k]%mod)*(y.num[k][j]%mod))%mod;
   			}
   		}
   	}
   	return c;
   }
   matrix operator ^ (int x) {
   	matrix c,xx;
   	xx=*this;
   	c.m=xx.m;
   	c.n=xx.n;
   	for(int i=1; i<=xx.n; i++)
   		for(int j=1; j<=xx.m; j++)
   			c.num[i][j]=(i==j);
   	for(; x; x>>=1) {
   		if(x&1)
   			c=c*xx;
   		xx=xx*xx;
   	}
   	return c;
   }
};int mod=1e9+7;
int fpow(int x,int y) { 
   int ans=1;int base=x;
   while(y) {
   	if(y&1){
   	ans=ans*base;
   	ans%=mod;	
   	}
   	y/=2;
   	base=base*base;
   	base%=mod;
   }
   return ans%mod;
}
const int maxn=500005;
int lim=maxn,tot=0;int prime[maxn];bool tof[maxn];
void shai() {
   for(int i=2; i<=lim; i++) {if(tof[i] == false) {prime[++tot] = i;}
   	for(int j=1; j<=tot && i * prime[j] <=lim; j++) {tof[i * prime[j]] = true;if(i % prime[j] == 0) break;}}
}
int head[maxn];
int id=0;
struct Edge {
   int w,v,next;
} p[maxn*5];
void build(int u,int v,int w) {
   p[++id].v=v;p[id].w=w;
   p[id].next=head[u];
   head[u]=id;return; 
}
int f[maxn],a[maxn];int n,m,t,k;
//加油 注意初始化
int ru[maxn];
vector<int>edg[maxn];
int dis[maxn];queue<int>q;
void dfs(int noww,int fa){
   if(fa!=0){
   	build(noww,fa,0);
   	ru[fa]++;
   }
   for(auto &it:edg[noww]){
   	if(it==fa)
   	continue;
   	dfs(it,noww);
   }
}
signed main() {
   ios::sync_with_stdio(false),cin.tie(NULL);
   //freopen("data.in","r",stdin);
   //freopen("T1.out","w",stdout);
   cin>>t;
   while(t--){
    cin>>n;
    int x,y;
    rep(i,1,n-1){
    	cin>>x>>y;
    	edg[x].push_back(y);
    	edg[y].push_back(x);
    	//build(x,y,0);
    //	build(y,x,0);
    //	ru[x]++;ru[y]++;
    } 
    dfs(1,0);
    int maxx=0;
    for(int i=1;i<=n;i++){
    	if(ru[i]==0){
    		q.push(i);
    		dis[i]=1;
    	//	f[0]++;
   	 }
    }
    while(!q.empty()){
    	int u=q.front();
    	q.pop();
    	f[dis[u]]++;
    	maxx=max(maxx,dis[u]);
    	for(int i=head[u];i;i=p[i].next){
    		int v=p[i].v;
    		ru[v]--;
    		if(ru[v]==0){
    			dis[v]=max(dis[v],dis[u]+1);
    			q.push(v);
   		 }
   	 }
    }
    rep(i,1,maxx){
    	a[i]=a[i-1]+f[maxx-i+1];
    	a[i]%=mod;
    }
   int ll=fpow(2,n-1);
   //cout<<ll;
   int anss=0;
   rep(i,1,maxx){
   	anss+=ll*a[i];
   	anss%=mod;
   }
   cout<<anss<<endl;
}
   return 0;
}
/*



*/