Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
34342 22fhq 【S】T3 C++ 通过 100 123 MS 17692 KB 1633 2024-11-06 09:28:25

Tests(10/10):


#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; }


测评信息: