Untitled

mail@pastecode.io avatar
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