提交时间:2024-11-05 18:54:37

运行 ID: 34297

#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair typedef long long ll; using namespace std; const int maxn=1e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,dep[maxn],f[maxn],deep[maxn],ct[maxn]; int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } vector<int>vec[maxn]; void dfs(int u,int fa){ for(int x:vec[u])if(x!=fa)dep[x]=dep[u]+1,dfs(x,u); } pi get(){ dfs(1,0); int mx=1;up(i,2,n)if(dep[mx]<dep[i])mx=i; up(i,1,n)dep[i]=0;dfs(mx,0); int pos=1;up(i,2,n)if(dep[pos]<dep[i])pos=i; up(i,1,n)dep[i]=0; return m_p(mx,pos); } void slv(){ n=read();up(i,1,n-1){int x=read(),y=read();vec[x].p_b(y),vec[y].p_b(x);} auto w=get(); dfs(w.p1,0);up(i,1,n)deep[i]=dep[i]; dep[w.p2]=0;dfs(w.p2,0); up(i,1,n)ct[max(deep[i],dep[i])]++; up(i,1,n)ct[i]+=ct[i-1]; int mn=0;up(i,1,n)deep[i]=min(deep[i],dep[i]); up(i,1,n)mn=max(mn,deep[i]); up(i,mn,dep[w.p1])f[i]=qp(2,ct[i]); up(i,mn,dep[w.p1]-1)(f[i]<<=1)%=mod; int res=0; up(i,mn,dep[w.p1])(res+=(f[i]-f[i-1]+mod)%mod*1ll*i%mod)%=mod; cout<<res; } int main(){ //freopen("color.in","r",stdin); //freopen("color.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }