Untitled
unknown
plain_text
a month ago
2.4 kB
2
Indexable
Never
#include<bits/stdc++.h> using namespace std; #define all(v) ((v).begin()),((v).end()) #define sz(v) (v.size()) #define yes cout<<"Yes"<<'\n'; #define no cout<<"No"<<'\n'; #define endl '\n'; #define f(i,j,k) for(long long i=j;i<k;i++) #define fb(i,j,k) for(long long i=j;i>=k;i--) #define fs(i,j,k,p) for(long long i=j;i<k;i+=p) #define fbs(i,j,k,p) for(long long i=j;i>=k;i-=p) #define pb push_back #define ppb pop_back #define mp make_pair #define ff first #define ss second #define pi 3.141592653589793238462 typedef long long ll; typedef unsigned long long ull; typedef long double lld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<vector<ll>> vvll; typedef vector<vector<int>> vvi; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pp ; typedef vector<ll> vll; #define int long long const int mod=1e9+7; long long pow(long long a, long long b, long long m) { a %= m; long long res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } vector<int>leaf(3e5,0); void dfs(int node,int p,vector<vector<int>>&adj,vector<int>&depth,vector<int>&sz) { depth[node]=depth[p]+1; sz[node]=1; int x=1; for(auto u:adj[node]) { if (u==p)continue; x=0; dfs(u,node,adj,depth,sz); sz[node]+=sz[u]; } leaf[node]=x; } void solve() { int n; cin>>n; vector<vector<int>>adj(n+1); for(int i=1;i<=n-1;++i) { int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } if (n==1) { cout<<0<<endl; return; } for (int i=0;i<=n;++i)leaf[i]=0; vector<int>depth(n+1,0); vector<int>se(n+1,0); dfs(1,1,adj,depth,se); int tot=0; ll y=0; for (int i=1;i<=n;++i) { if (leaf[i]) { tot+=pow(2,depth[i]-2,mod); tot%=mod; y+=(((depth[i]-2)*pow(2,depth[i]-3,mod))%mod+(pow(2,depth[i]-2,mod))%mod)%mod; y%=mod; } } cout<<(y*pow(tot,mod-2,mod))%mod<<endl; } signed main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); // freopen("jumper.in","r",stdin); int t; t=1; cin>>t; while(t--) { solve(); } }
Leave a Comment