星の特徴になっているのは中心なので, 中心を軸に考える. 星において,中心から出てる頂点を葉と呼ぶことにする.
\(T\)において degree が 1の頂点は, もとのグラフで星の中心にならない. また,
星\(S_{0}\)の中心 \(\rightarrow \) \(S_{0}\)の葉 \(\rightarrow \) 星\(S_{1}\)の葉 \(\rightarrow \) \(S_{1}\)の中心
と移動することができる.
つまり,星の中心同士の距離が 3になる.
実装: DFS
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n;
m = n-1;
vvll to(n);
rep(i,m){
ll a,b; cin >> a >> b;
--a, --b;
to[a].push_back(b);
to[b].push_back(a);
}
vll ans;
ans.push_back(to[cu].size());
}
}
};
rep(i,n){
if(to[i].size() == 1){
dfs(dfs, i);
break;
}
}
sort(all(ans));
coutv(ans);
return 0;
}