AT_arc108_f

讲的题，但是没听而且感觉挺有意思而且见过类似的，于是自己做出来了。

首先有关键性质：若最大距离的同色点对为 $u,v$，树上的任意一条直径 $(s,t)$ 满足 $s=u,s=v,t=u,t=v$ 其中至少一个成立。

证明：反证。若有一条直径两端点为 $s,t$ 且 $u,v$ 不是任何的一个 $s$ 或 $t$，$s,t,u,v$ 互不相同，钦定 $dis(s,u)<dis(t,u)$，则 $col_u\not=col_t$。同时，因为 $(s,t)$ 为直径，$dis(u,t)<dis(s,t)$，$dis(u,v)<dis(s,v)$，于是 $col_s\not=col_v$，又 $col_u=col_v$，则 $col_s=col_t$，此时显然 $s,t$ 同色且距离更远，不成立。

所以先找出任意一条直径 $(s,t)$，有 $2^{n-1}$ 种情况同色，答案为 $dis(s,t)$。否则，钦定 $col_s=0$，对于每个点 $u$ 考虑钦定 $col_u=0/1$ 的时，有多少种情况使得 $u$ 与一个直径端点的距离是最终答案。

预处理出 $\max(dis(u,s),dis(u,t))$ 然后排序后，处理出此时选这个点做答案的其中一个端点是否可行（$\max(dis(u,s),dis(u,t))\ge\max_{v\not=u}\min(dis(v,s),dis(v,t))$）有多少点 $v$ 是 $col_v$ 为 $0/1$ 都行（即为排序后排名 $-1$），然后计算即可。最后将这部分贡献 $\times 2$，因为加上 $col_s=1$ 的情况。

code：

int n,m,dis[N],g[N],h[N],pw[N],pos;
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
void dfs(int u,int f){
	if((dis[u]=dis[f]+1)>dis[pos]){
		pos=u;
	}
	go(i,u){
		int v=e[i].to;
		if(v==f){
			continue;
		}
		dfs(v,u);
	}
}
void getDis(int u,int f,int *d){
	go(i,u){
		int v=e[i].to;
		if(v==f){
			continue;
		}
		d[v]=d[u]+1,getDis(v,u,d);
	}
}
void Yorushika(){
	scanf("%d",&n);
	rep(i,1,n-1){
		int u,v;scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	int u,v;
	dfs(1,0),u=pos,pos=0;
	dfs(u,0),v=pos;
	getDis(u,0,g),getDis(v,0,h);
	pw[0]=1;
	rep(i,1,n){
		pw[i]=2*pw[i-1]%mod;
	}
	int ans=1ll*pw[n-1]*g[v]%mod;
	rep(i,1,n){
		if(g[i]>h[i]){
			swap(g[i],h[i]);
		}
	}
	sort(g+1,g+n+1),sort(h+1,h+n+1);
	rep(i,1,n-2){
		if(g[n]>h[i]){
			continue;
		}
		ans=Mod(ans,2ll*h[i]*pw[i-1]%mod);
	}
	int p=lower_bound(h+1,h+n-1,g[n])-h-1;
	ans=Mod(ans,2ll*g[n]*pw[p]%mod);
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}