提出 #9220560

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

struct modint{
    using i64=int_fast64_t;
    i64 a;
    static constexpr i64 MOD=1e9+7;
    modint(){a=0;}
    modint(i64 a_){
        a=a_%MOD;
        if(a<0) a+=MOD;
    }
    modint inv()const{
        i64 n=1,m=MOD-2,A=a;
        while(m){
            if(m&1)(n*=A)%=MOD;
            (A*=A)%=MOD;
            m>>=1;
        }
        modint y(n);
        return y;
    }
    bool operator==(const modint& x){
        return a==x.a;
    }
    bool operator!=(const modint& x){
        return a!=x.a;
    }
    modint& operator=(const modint& x){
        a=x.a;
        return *this;
    }
    modint operator+(const modint& x){
        modint y;
        y.a=a+x.a;
        if(y.a>MOD) y.a-=MOD;
        return y;
    }
    modint operator-(const modint& x){
        modint y;
        y.a=a-x.a;
        if(y.a<0) y.a+=MOD;
        return y;
    }
    modint operator*(const modint& x){
        modint y;
        y.a=(a*x.a)%MOD;
        return y;
    }
    modint operator/(const modint& x){
        modint y;
        y.a=(a*x.inv().a)%MOD;
        return y;
    }
    modint& operator+=(const modint& x){
        a+=x.a;
        if(a>=MOD) a-=MOD;
        return *this;
    }
    modint& operator-=(const modint& x){
        a-=x.a;
        if(a<0) a+=MOD;
        return *this;
    }
    modint& operator*=(const modint& x){
        (a*=x.a)%=MOD;
        return *this;
    }
    modint& operator/=(const modint& x){
        (a*=x.inv().a)%=MOD;
        return *this;
    }
};
istream& operator>>(istream &in,modint& x){
    int_fast64_t a_;
    in>>a_;
    modint y(a_);
    x=y;
    return in;
}
ostream& operator<<(ostream &out,const modint& x){
    out<<x.a;
    return out;
}
modint pwr(int_fast64_t a,int_fast64_t b){
    modint _;
    int_fast64_t n=1,A=a;
    while(b){
        if(b&1) (n*=A)%=modint::MOD;
        (A*=A)%=modint::MOD;
        b>>=1;
    }
    _.a=n;
    return _;
}

struct tree{
    size_t n,r,md;
    vector<vector<int>> e;
    vector<int> pa,d,sz;
    explicit tree(int n_){
        n=n_;
        e.resize(n);
    }
    void add(int a,int b){
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    void r_dfs(int i,int p=-1,int D=0){
        sz[i]=1;
        pa[i]=p;d[i]=D;md=max(md,(size_t)D);++D;
        for(auto j:e[i]) if(j!=p){
            r_dfs(j,i,D);
            sz[i]+=sz[j];
        }
    }
    void r_i(int r_){
        pa.resize(n);d.resize(n);sz.resize(n);r=r_;md=0;
        r_dfs(r);
    }
    int r2(){
        r_i(0);
        int m=0,M=0;
        fr(i,n) m=max(m,d[i]);
        fr(i,n) if(d[i]==m) M=i;
        pa.clear(),d.clear();
        r_i(M);
        m=0;
        fr(i,n) m=max(m,d[i]);
        return m;
    }
    modint solve(int n,int i){
        modint c;
        for(auto j:e[i]) if(sz[i]>sz[j]){
            c+=pwr(2,sz[j])-1;
        }
        c+=pwr(2,n-sz[i]);
        return pwr(2,n-1)-c;
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int n,a,b;
    in>>n;
    tree t(n);
    fr(i,n-1){
        in>>a>>b;
        t.add(--a,--b);
    }
    t.r_i(0);
    modint ans{};
    fr(i,n) ans+=t.solve(n,i);
    ans/=pwr(2,n);
    cout<<ans<<endl;
}

提出情報

ジャッジ結果