Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
34301 liuyile 【S】T3 C++ 解答错误 0 78 MS 23952 KB 1522 2024-11-05 19:08:54

Tests(0/10):


#include<bits/stdc++.h> using namespace std; #define int long long // #define endl "\n" #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second // #pragma GCC optimize("Ofast") int n; vector<int>g[200300]; int a,b,mxd,da[200300],db[200300]; int fa[200300],fb[200300]; inline void dfs(int u,int *d,int *f){ d[u]=d[f[u]]+1; if(d[u]>d[mxd])mxd=u; for(int v:g[u])if(v!=f[u]){ f[v]=u; dfs(v,d,f); } } int c[200300]; int f[203000],h[200300]; const int M=1e9+7; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; a=a*a%M; x>>=1; } return res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("genshin.in","r",stdin); // freopen("genshin.out","w",stdout); cin>>n; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } a=1; dfs(a,da,fa); memset(fa,0,sizeof(fa)); memset(da,0,sizeof(da)); a=mxd; dfs(a,da,fa); b=mxd; int len=da[mxd]-1; dfs(b,db,fb); int L=0; int res=qp(2,n-1)*len%M; // cout<<a<<" "<<b<<" "<<len<<" "<<res<<endl; for(int i=1;i<=n;i++){ L=max(L,min(da[i],db[i])-1); if(a!=i&&b!=i) c[max(da[i],db[i])-1]++; } for(int i=L;i<=n;i++)c[i]+=c[i-1],f[i]=qp(2,c[i]),h[i]=(f[i]-f[i-1]+M)%M,res=(res+2*i*h[i])%M; cout<<res<<endl; return 0; }


测评信息: