「HDU6810」Imperative Meeting

2020 年 07 月 30 日

给定 $n$ 个点的树，定义 $m$ 个人的约会点 $x$ 为使得 $m$ 个人所在的点到 $x$ 的距离之和最小的点。

$m$ 个人所在位置在 $n$ 个点中随机选择（即总方案数 $\binom nm$ ），问所有方案到约会点距离之和的和。

$n \leq 10^6$ ，答案对 $10^9 + 7$ 取模。

题解

考虑确定 $m$ 个点后，所有人到某个点的距离和是单调的，也就是说可能称为约会点的点一定是一个联通块。

我们预处理出所有点到某个点的距离和，因为稍后我们选点时，（某一选点范围内）每个点被选中的概率是均等的。

「Part1」一个点能够成为约会点当且仅当每棵子树内选的点个数都 $\leq \frac m 2$ ，我们枚举点 $u$ 和其一个子树 $v$ ，使得 $v$ 内选的点的个数 $> \frac m 2$ （对于一种方案和固定的 $u$ ，这样的 $v$ 至多只有一个）。贡献形如

\sum_{\frac m 2 < i \leq m} \binom {siz_v} {i} \binom {n - siz_v} {m - i} \left( \frac {i} {siz_v} \cdot (sumsub_v + siz_v) + \frac {m - i} {n - siz_v} \cdot (sumall_u - sumsub_v - siz_v)\right)

这个分数可以合到组合数里，也就是瓶颈为

\sum_{\frac m2 < i \leq m} \binom si \binom {n-s} {m-i}

这个东西我们考虑组合意义，容易从 $f_s$ 递推到 $f_{s-1}$ 。

「Part2」一条边上的两个点能同时成为约会点当且仅当两侧被选中的点的个数都恰为 $\frac m 2$ ，这一部分容易直接计算。

于是点减边就做完了，时间复杂度 $O(n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9, mod = 1e9 + 7;
int T, n, m, fa[N], siz[N];
vector<int> G[N];
struct z {
  int x;
  z(int x = 0) : x(x) {}
  friend inline z operator*(z a, z b) { return (long long)a.x * b.x % mod; }
  friend inline z operator-(z a, z b) { return (a.x -= b.x) < 0 ? a.x + mod : a.x; }
  friend inline z operator+(z a, z b) { return (a.x += b.x) >= mod ? a.x - mod : a.x; }
} F0[N], F1[N], fac[N], inv[N], ifac[N], sumall[N], sumsub[N];
inline z fpow(z a, int b) {
  z s = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) s = s * a;
  return s;
}
inline z finv(z a) { return fpow(a, mod - 2); }
inline z C(int n, int m) { return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m]; }
struct atom {
  int siz;
  z sum;
};
vector<atom> A[N];
void dfs(int u) {
  siz[u] = 1;
  sumsub[u] = 0;
  for (int v : G[u]) {
    fa[v] = u, dfs(v), siz[u] += siz[v];
    sumsub[u] = sumsub[u] + sumsub[v] + siz[v];
  }
}
void dfs2(int u, z fr) {
  sumall[u] = fr + sumsub[u], fr = fr + n;
  for (int v : G[u]) {
    fr = fr + sumsub[v] + siz[v];
  }
  for (int v : G[u]) {
    dfs2(v, fr - sumsub[v] - siz[v] - siz[v]);
  }
}
void sol0(int n, int m, int l, int r, z *F) {
  if (l > m || l > r) {
    memset(F, 0, (n + 1) << 2);
  } else {
    F[n] = C(n, m);
    for (int i = n - 1; i >= 0; i--) F[i] = F[i + 1] - C(i, l - 1) * C(n - i - 1, m - l);
    for (int j = m + 1; j <= r; j++)
      for (int i = 0; i <= n; i++) F[i] = F[i] + C(i, j) * C(n - i, m - j);
  }
}
z sol1() {
  z res = 0;
  for (int u = 1; u <= n; u++) {
    res = res + C(n - 1, m - 1) * sumall[u];
    for (auto &x : A[u]) {
      res = res - F0[x.siz - 1] * (x.sum + x.siz) - F1[x.siz] * (sumall[u] - x.sum - x.siz);
    }
  }
  return res;
}
z sol2() {
  if (m & 1) return 0;
  z res = 0;
  for (int u = 1; u <= n; u++)
    for (auto &x : A[u]) {
      res = res + C(x.siz, m >> 1) * C(n - x.siz, m >> 1) * (inv[x.siz] * (x.sum + x.siz) + inv[n - x.siz] * (sumall[u] - x.sum - x.siz));
    }
  return res * (m >> 1) * finv(2);
}
int main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  fac[0] = ifac[0] = inv[0] = inv[1] = 1;
  for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i;
  for (int i = 2; i < N; i++) inv[i] = (mod - mod / i) * inv[mod % i];
  for (int i = 1; i < N; i++) ifac[i] = ifac[i - 1] * inv[i];
  for (cin >> T; T--;) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) G[i].clear(), A[i].clear();
    for (int fa, i = 2; i <= n; i++) {
      cin >> fa;
      G[fa].push_back(i);
    }
    dfs(1);
    dfs2(1, 0);
    for (int u = 1; u <= n; u++) {
      for (int v : G[u]) A[u].push_back({siz[v], sumsub[v]});
      A[u].push_back({n - siz[u], sumall[fa[u]] - sumsub[u] - siz[u]});
    }
    int l = (m >> 1) + 1;
    sol0(n - 1, m - 1, l - 1, m - 1, F0);
    sol0(n - 1, m - 1, l, m, F1);
    cout << (sol1() - sol2()).x << '\n';
  }
}

TABLE OF CONTENTS

题解

代码

题解

代码

评论