AtCoder Beginner Contest 221 F - Diameter set
题意
给定一棵树,找出有多少种点的集合,满足集合内的点两两间的距离均为树的直径。
大致解法
关键在于树直径的性质:
- 树的所有直径均交与一点
- 所有直径的交点为直径的中点(可能在边上)
可以感性的理解下,反证法也很容易证,于是我们可以以这个交点作为树的根,统计下每颗子树有多少叶子的深度是D/2,再统计答案即可,为了防止中点出现在边上,我们可以把边都扩大两倍,这样直径一定的偶数,中点一定是一个点。
code
const int N = 5e5+5;
const int mod = 998244353;
int n,m;
vector<int> ver[N];
int d[N],f[N];
int a,b,D;
void dfs(int x,int fa){
d[x] = d[fa] + 1;
f[x] = fa;
for(int y:ver[x]){
if(y == fa) continue;
dfs(y,x);
}
if(d[x]>d[b]) b = x;
}
ll ans,nm;
ll num,nnm;
void dfs2(int x,int fa){
d[x] = d[fa]+1;
if(d[x]-1 == D/2) nm++;
for(int y:ver[x]){
if(y == fa) continue;
dfs2(y,x);
if(fa == 0){
ans = ans * (nm+1) % mod;
num = (num+nm)%mod;
nm = 0;
}
}
if(fa == 0){
ans = (ans + mod - num)%mod;
}
}
ll qpow(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res * a % mod;
b>>=1;
a = a * a % mod;
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
ver[x].pb(n+i);
ver[n+i].pb(x);
ver[y].pb(n+i);
ver[n+i].pb(y);
}
dfs(1,0);
a=b;
b=0;
dfs(a,0);
D = d[b]-1;
int m = D/2,now = b;
while(m--) now = f[now];
ans = 1;
dfs2(now,0);
ans = ((ans-1)%mod+mod)%mod;
printf("%lld\n",ans);
}