Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
34342 | 22fhq | 【S】T3 | C++ | 通过 | 100 | 123 MS | 17692 KB | 1633 | 2024-11-06 09:28:25 |
#include<bits/stdc++.h> using namespace std; #define int long long int n; vector<int>e[200005]; int dp[200005][2]; void dfs(int p,int f,int id){ // cout<<p<<endl; for(int x:e[p]){ // cout<<p<<" "<<x<<endl; if(x==f)continue; dp[x][id]=dp[p][id]+1; dfs(x,p,id); } } int cnt[200005],p[200005]; int f[200005]; const int mod=1e9+7; void slv(){ 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); } // for(int i=1;i<=n;i++){ // for(int x:e[i])cout<<x<<" ";cout<<endl; // } dfs(1,0,0); int mx=1; for(int i=2;i<=n;i++){ if(dp[i][0]>dp[mx][0])mx=i; } int nd1=mx; dp[mx][0]=0; dfs(mx,0,0); mx=1; for(int i=2;i<=n;i++){ if(dp[i][0]>dp[mx][0])mx=i; } int nd2=mx; dfs(mx,0,1); for(int i=1;i<=n;i++){ if(i==nd1||i==nd2)continue; cnt[max(dp[i][0],dp[i][1])]++; } for(int i=1;i<=n;i++){ cnt[i]+=cnt[i-1]; } p[0]=1; for(int i=1;i<=n;i++){ p[i]=p[i-1]*2; p[i]%=mod; } int ans=0; int l=0; for(int i=1;i<=n;i++)l=max(min(dp[i][0],dp[i][1]),l); for(int i=l;i<=dp[nd1][1];i++){ // cout<<i<<endl; // cout<<cnt[i]<<endl; f[i]=p[cnt[i]]; ans+=(f[i]-f[i-1])*i%mod; ans%=mod; } ans*=2; ans%=mod; ans+=p[n-1]*dp[nd1][1]; ans%=mod; cout<<ans; } signed main(){ // int T; // cin>>T; // while(T--) slv(); return 0; }