Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
34317 | A21μΘ_wjy | 【S】T3 | C++ | 通过 | 100 | 120 MS | 17684 KB | 1263 | 2024-11-05 21:21:36 |
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=2e5+7; const int mod=1e9+7; int n; vector<int> E[maxn]; int cnt[maxn]; int f[maxn]; int g[maxn]; int D1[maxn],D2[maxn]; int L1,L2; inline void DFS(int u,int *dis,int f){ for(auto v:E[u]){ if(v!=f)dis[v]=dis[u]+1,DFS(v,dis,u); } } int P[maxn]; inline void InitP2(){ P[0]=1; for(int i=1;i<=n;i++)P[i]=(P[i-1]<<1)%mod; } inline void slv(){ int LB=0,RB=D1[L2]; for(int i=1;i<=n;i++)if(i!=L1&&i!=L2)LB=max(LB,min(D1[i],D2[i])); for(int i=1;i<=n;i++)if(i!=L1&&i!=L2)cnt[max(D1[i],D2[i])]++; for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1]; int ans=0; for(int i=LB;i<=RB;i++){ f[i]=P[cnt[i]]; if(i)g[i]=(f[i]-f[i-1]+mod)%mod; (ans+=i*g[i]%mod)%=mod; } (ans*=2)%=mod; (ans+=P[n-1]*RB%mod)%=mod; cout<<ans<<endl; return; } signed main(){ cin>>n; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; E[u].push_back(v),E[v].push_back(u); } DFS(1,D2,0); for(int i=1;i<=n;i++)if(!L1||D2[i]>D2[L1])L1=i; DFS(L1,D1,0); for(int i=1;i<=n;i++)if(!L2||D1[i]>D1[L2])L2=i; D2[L2]=0,DFS(L2,D2,0); InitP2(); slv(); }