题解 - Luogu P10309 「Cfz Round 2」Max of Distance

简述题意

给定一棵包含 $n$ 个结点的树和一个整数 $E$。构造树中每条边的整数边权 $w_i(1\le w_i\le 10^9)$，满足均匀随机选择一个结点 $u$，$\max\limits_{v=1}^n\operatorname{dis}(u,v)$ 的期望对 $998244353$ 取模的值等于 $E$；或报告无解。$2\le n\le 10^5$，$1 \le u_i,v_i \le n$，$0\le E < 998244353$。

分析

我们发现题目中的关键点既有 $\max$，又有期望，还有取模。就可以猜这个 $\max$ 是这其中关键要着手的。

一般地，树上的 $\max\limits_{v=1}^n\operatorname{dis}(u,v)$ 取到的 $v$ 是一个直径的端点，是一个叶子；那么，我们就直接钦定一个 $v$，让其他点都是到 $v$ 最远，而 $v$ 走直径就可以了。

具体的办法就是，随便选一个叶子 $v$，把与 $v$ 相连的唯一一条边设定一个 $\ge n$ 的权值，而其他的边权都设为 $1$。接下来只需要求出这个权值 $w$。

由题意，我们有 $w+\frac{1}{n}(\max_{u\neq v} d_u + \sum_{u\neq v} d_u)\equiv E\pmod {998244353}$，其中 $d_u$ 表示以 $v$ 为根，$u$ 点的深度 $-1$。

$d$ 可以直接通过 dfs 求出来，那么 $w$ 也就容易得到了。

最后为了确认满足这条边必走，如果 $w<n$，就让 $w$ 加上 $998244353$，这样也不会超出 $10^9$。

由以上的构造，可以发现恒有解。

时间复杂度 $O(n+\log V)$。

代码

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

const int MXN = 100005;
const int DVS = 998244353;
int N, deg[MXN], eid[MXN], E, spid, mxd, diff;
vector<int> to[MXN];

void dfs(int p, int f, int d) {
  mxd = max(mxd, d);
  if (f != -1) diff = (diff + d - 1) % DVS;
  for (int q : to[p]) {
    if (q == f) continue;
    dfs(q, p, d + 1);
  }
}
int inv(int x) {
  int p(DVS - 2), a(1);
  while (p) {
    if (p & 1) a = a * 1LL * x % DVS;
    x = x * 1LL * x % DVS;
    p >>= 1;
  }
  return a;
}

int main() {
  cin >> N;
  for (int i(1), x(0), y(0); i != N; ++i) {
    cin >> x >> y;
    --x, --y;
    ++deg[x], ++deg[y];
    eid[x] = eid[y] = i;
    to[x].push_back(y);
    to[y].push_back(x);
  }
  cin >> E;
  for (int i(0); i != N; ++i) {
    if (deg[i] != 1) continue;
    spid = eid[i];
    dfs(i, -1, 0);
    diff = (diff + mxd - 1) % DVS;
    break;
  }
  diff = diff * 1LL * inv(N) % DVS;
  E = (E - diff + DVS) % DVS;
  if (E < N) E += DVS;
  for (int i(1); i != N; ++i) {
    if (i == spid) cout << E << endl;
    else cout << '1' << endl;
  }
  return 0;
}