木の中心

木の直径を \(D\) とし、木の直径の中心に注目します。 この点は直径が偶数なら頂点になり、奇数なら辺の中心点になります。 全ての辺の中心点に頂点を \(1\) つずつ挿入すると、直径 \(D'\) は \(2D\) になり、直径の中心は頂点になります。以降は頂点を追加したこのグラフについて考えます。

直径の中心を根とした根付き木を考えます。すると、以下の性質が成り立ちます。

• どの頂点も根までの距離が \(D'/2\) 以下
• 根にくっついている部分木を \(2\) つ選び、根からの距離がちょうど \(D'/2\) である頂点をそれぞれの部分木から \(1\) つずつ選ぶと、それらの距離は直径となる。

解法

根付き木に対して、以下の dp を求めます。

• \(dp[v] = \) 頂点 \(v\) 以下の部分木内の頂点の \(v\) までの距離の最大値とそれを達成する頂点の個数

この情報があれば、木の直径・直径の中心・問題の答え、をそれぞれ求めることが出来ます。 （直径・直径の中心については、余談の方法で素直に求めた方が分かりやすいかもしれません。）

直径

各頂点について、その頂点を LCA とするような頂点対の距離の最大値を求め、それらの最大値を求めます。

直径の中心

\(dp[v].val = D'/2\) である頂点が直径の中心となります。正当性：

• 直径の中心について \(dp[v].val = D'/2\) となることは上記の性質より明らか
• 直径の中心以外について \(dp[v].val = D'/2\) とならない
  • 中心の子孫：明らかに \(dp[v].val \lt D'/2\)
  • 中心の先祖：明らかに \(dp[v].val \gt D'/2\)
  • それ以外（中心の先祖から枝分かれした子孫）：\(dp[v].val \ge D'/2\) だとすると長さ \(D'\) より長いパスが存在することになり矛盾

問題の答え

異なる集合から \(1\) つずつ選ぶ場合の数を求める問題を解けば良いです。

実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct MaxNum {
  int val = -1, num = 0;
  MaxNum operator+(const MaxNum& a) const {
    if (val < a.val) return a;
    if (val > a.val) return *this;
    return MaxNum(val, num+a.num);
  }
  void operator+=(const MaxNum& a) { *this = *this+a;}
};

int main() {
  int n;
  cin >> n;
  int N = n*2-1;
  vector<vector<int>> to(N);
  for (int i = 0; i < n-1; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    to[a].push_back(n+i); to[n+i].push_back(a);
    to[b].push_back(n+i); to[n+i].push_back(b);
  }

  int diameter = 0;
  vector<MaxNum> dp(N);
  auto dfs = [&](auto dfs, int v, int p=-1) -> MaxNum {
    dp[v] = MaxNum(0,1);
    for (int u : to[v]) if (u != p) {
      auto mn = dfs(dfs,u,v);
      mn.val++;
      diameter = max(diameter, dp[v].val + mn.val);
      dp[v] += mn;
    }
    return dp[v];
  };
  dfs(dfs,0);

  int c = 0;
  for (int v = 0; v < N; v++) {
    if (dp[v].val == diameter/2) c = v;
  }

  dfs(dfs,c);
  ll ans = 0, sum = 0;
  for (int v : to[c]) {
    if (dp[v].val+1 != diameter/2) continue;
    ans += sum * dp[v].num;
    sum += dp[v].num;
  }
  cout << ans << endl;
  return 0;
}

余談

木の直径だけならば double-sweep というアルゴリズムで簡単に求めることが出来ます。

1. 適当な頂点から最も遠い点を \(a\) とする
2. \(a\) から最も遠い点を \(b\) とする
3. \((a,b)\) の組は直径を成す

正当性は木の中心の性質から簡単に示すことが出来ます。