提交时间:2024-11-05 19:22:17

运行 ID: 34305

#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=200010,Mod=1000000007,inf=100000000; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} int n,m,ans,x,y,len; pii f[MAXN]; void dfs(int u,int lst){ f[u]=mk(0,u); for(inx(u))if(v!=lst){ dfs(v,u); if(f[u].fr+f[v].fr+1>ans){ ans=f[u].fr+f[v].fr+1; x=f[u].sc,y=f[v].sc; } f[u]=max(f[u],mk(f[v].fr+1,f[v].sc)); } if(f[u].fr>ans){ ans=f[u].fr; x=u,y=f[u].sc; } } int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod;y>>=1;}return rt;} int dep[MAXN][2],L,cnt[MAXN],g[MAXN]; void dfs2(int u,int lst,bool ty){ for(inx(u))if(v!=lst){ dep[v][ty]=dep[u][ty]+1; dfs2(v,u,ty); } } void slv(){ n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); add_side(u,v); } dfs(1,1),len=ans; dfs2(x,x,0),dfs2(y,y,1); for(int i=1;i<=n;i++)if(i!=x&&i!=y)L=max(L,min(dep[i][0],dep[i][1])),cnt[max(dep[i][0],dep[i][1])]++; for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1]; for(int i=L;i<=n;i++)g[i]=Pow(2,cnt[i]); ans=ans*Pow(2,n-1)%Mod; for(int i=len;i>=L;i--)g[i]=(g[i]+Mod-g[i-1])%Mod,ans=(ans+g[i]*i%Mod*2%Mod)%Mod; // for(int i=1;i<=len;i++)cout<<i<<" "<<g[i]<<" "<<cnt[i]<<endl; printf("%lld",ans); } signed main(){ slv(); return 0; }