ABC482 E - Diameter Endpoint Colors
- サイト
- AtCoder
- コンテスト
- ABC482
- 問題
- E - Diameter Endpoint Colors
- 難易度
- 1531
頂点の木 があり、頂点 は色 で塗られています。同じ色で、間の距離(パスの辺の本数)が木の直径と等しい頂点の組 ()の個数を求める問題です()。
直径の両端になる組
Section titled “直径の両端になる組”直径の長さを とします。木の直径の中点を中心と呼ぶと、距離がちょうど になる組は中心を使って次のように分けられます。
- が偶数のとき、中心は頂点 です。どの頂点も からの距離が 以下なので、距離が になる組は、 からの距離がどちらも で、パスが を通るもの、つまり の異なる隣接頂点の側(部分木)にあるものです。
- が奇数のとき、中心は辺 です。この辺を除いて 側と 側に分けると、距離が になる組は、 側で からの距離が の頂点と、 側で からの距離が の頂点の組です。
どちらの場合も、直径の端点になる頂点をいくつかのグループに分けると、「距離が になる」ことと「異なるグループに属する」ことが同値になります。偶数のときは の隣接頂点ごと、奇数のときは 側と 側の つがグループです。
同じ色の組を数える
Section titled “同じ色の組を数える”あとは、異なるグループにある同じ色の頂点の組を数えればよいです。グループを順に見ていき、色ごとに「それまでのグループに含まれる頂点の個数」を持っておきます。各頂点について、その色の個数を答えに足してから、グループ内の頂点をまとめて個数に加えます。
直径と中心は BFS を 回するなどして求められるので、全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/graph/tree.hpp"#include "shogo-library/graph/tree_util.hpp"#include "shogo-library/utility/vector_func.hpp"
void solve() { LL(N); Tree<ll> tree(N); tree.read(); VL(C, N); C--; vl cnt(N); ll ans = 0; for (auto g : tree_diameter_endpoint_groups(tree)) { for (ll u : g) ans += cnt[C[u]]; for (ll u : g) cnt[C[u]]++; } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}tree_diameter_endpoint_groups は、上の解法のとおり直径の端点をグループに分けて返す関数です。C-- で色を 0 始まりにし、cnt に色ごとの個数を持っています。
使用ライブラリ:cpp_include@cb82602