コンテンツにスキップ

ABC482 E - Diameter Endpoint Colors

サイト
AtCoder
コンテスト
ABC482
問題
E - Diameter Endpoint Colors
難易度
1531

NN 頂点の木 TT があり、頂点 vv は色 CvC_v で塗られています。同じ色で、間の距離(パスの辺の本数)が木の直径と等しい頂点の組 (u,v)(u, v)(u<vu < v)の個数を求める問題です(N≤2×105N \le 2 \times 10^5)。

直径の長さを DD とします。木の直径の中点を中心と呼ぶと、距離がちょうど DD になる組は中心を使って次のように分けられます。

  • D=2rD = 2r が偶数のとき、中心は頂点 cc です。どの頂点も cc からの距離が rr 以下なので、距離が DD になる組は、cc からの距離がどちらも rr で、パスが cc を通るもの、つまり cc の異なる隣接頂点の側(部分木)にあるものです。
  • D=2r+1D = 2r + 1 が奇数のとき、中心は辺 (c1,c2)(c_1, c_2) です。この辺を除いて c1c_1 側と c2c_2 側に分けると、距離が DD になる組は、c1c_1 側で c1c_1 からの距離が rr の頂点と、c2c_2 側で c2c_2 からの距離が rr の頂点の組です。

どちらの場合も、直径の端点になる頂点をいくつかのグループに分けると、「距離が DD になる」ことと「異なるグループに属する」ことが同値になります。偶数のときは cc の隣接頂点ごと、奇数のときは c1c_1 側と c2c_2 側の 22 つがグループです。

あとは、異なるグループにある同じ色の頂点の組を数えればよいです。グループを順に見ていき、色ごとに「それまでのグループに含まれる頂点の個数」を持っておきます。各頂点について、その色の個数を答えに足してから、グループ内の頂点をまとめて個数に加えます。

直径と中心は BFS を 22 回するなどして求められるので、全体の計算量は O(N)O(N) です。

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