题目描述
Sol
首先求出树的直径,两个端点\(S,T\) 。
显然如果\(S,T\)同色,那答案此时肯定是直径。
我们算出每个点到\(S\)的距离\(ds_i\) ,到\(T\)的距离\(dt_i\)
那这个点可能产生的贡献为\(max(ds_i,dt_i)\) ,把这个用\(cnt\)统计下来。
可能的最小贡献\(mn\)为\(max(min(ds_i,dt_i))\)
我们考虑枚举每一种可能的贡献\(sum\),计算所有\(>=i\)的贡献。
\(sum\)从\(0\)到\(mn-1\)的贡献:\(2^n\)
\(sum\)从\(mn\)到直径的贡献:\(2^n-2^{cnt_i+1}\)
取模记得用快的方法。
Code
#include<bits/stdc++.h>
#define N (200010)
#define M (400010)
#define P (1000000007)
#define ll long long
using namespace std;
struct xbk{int ed,nx;}e[M];
int n,mn,tot,ds[N],dt[N],cnt[N],dep[N],head[N];
ll p[N];
inline int read(){
int w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
inline void add(int a,int b){
e[++tot].ed=b;
e[tot].nx=head[a];
head[a]=tot;
}
inline int dfs(int st,int fa){
dep[st]=dep[fa]+1;
int res=st;
for(int i=head[st];i;i=e[i].nx){
int ed=e[i].ed;
if(ed==fa) continue;
int now=dfs(ed,st);
if(dep[now]>dep[res]) res=now;
}
return res;
}
int main(){
n=read();
p[0]=1;
for(int i=1;i<n;i++){
int u=read(),v=read();
add(u,v),add(v,u);
}
for(int i=1;i<=n+1;i++){
p[i]=p[i-1]<<1;
if(p[i]>P) p[i]-=P;
}
int S=dfs(1,0);
int T=dfs(S,0);
for(int i=1;i<=n;i++) ds[i]=dep[i]-1;
dfs(T,0);
for(int i=1;i<=n;i++) dt[i]=dep[i]-1;
for(int i=1;i<=n;i++) ++cnt[max(ds[i],dt[i])],mn=max(mn,min(ds[i],dt[i]));
for(int i=1;i<n;i++) cnt[i]+=cnt[i-1];
ll ans=0;
for(int i=0;i<mn;i++){
ans=ans+p[n];
if(ans>P) ans-=P;
}
for(int i=mn;i<dt[S];i++){
ans=(ans+p[n]-p[cnt[i]+1]);
if(ans<0) ans+=P;
if(ans>P) ans-=P;
}
printf("%lld\n",ans);
return 0;
}