题解 CF566C 【Logistical Questions】

> [CF566C Logistical Questions](https://codeforces.com/contest/566/problem/C) ## 题意 - 一棵 $n$ 个节点的树，点有点权，边有边权。 - 两点间的距离定义为两点间边权和的 $\frac 32$ 次方。 - 求这棵树的带权重心。 - $n \le 2 \times 10^5$。 ## 题解 设 $d(x,y)$ 为 $x,y$ 的距离，即 $\text{dist}(x,y)^{\frac 32}$，**在这里，我们不要求 $x,y$ 为树中的节点，即 $x,y$ 也可以为某条边中的点**。 首先可以注意到，对于树上的任意一条路径 $[a,b]$，若点 $x \in [a,b]$，则对于一个点 $i$，$d(x,i)$ 是一个下凸函数。 设 $f(x) = \sum_{i=1}^n d(x,i)$，由于凸函数之和仍为凸函数，因此 $f(x)$ 仍是一个下凸函数。 因此，**整棵树有且仅有一个点 $x$ 能取到 $f(x)$ 的最小值，且从这个点向外 $f(x)$ 逐渐变大**。 如果树退化为一条链，则可以二分 $x$。当还原到树上，同理可以**点分治**找到 $x$。 点分治到某个点 $x$ 时，首先用 $x$ 更新答案，然后找到能使 $f(x)$ 变小的子树继续点分。根据刚才的讨论，这样的子树最多只有一个。 如何找到这个子树呢？如果每个子树暴力计算一遍 $f(x)$ 肯定不行。 考虑**求导**。设 $x$ 共有 $k$ 个子树，第 $i$ 个子树的根（即 $x$ 的第 $i$ 个儿子）为 $t_i$，这个子树中所有项的导数和为 $p_i$。 则从 $x$ 向 $t_i$ 移动时 $f(x)$ 的导数为 $\sum_{j=1}^k p_j - 2p_i$，找到这个值为负数的子树即可。 时间复杂度 $\mathcal O(n \log n)$。 ## 代码 ```cpp const int N = 2e5 + 7; int n, w[N], s[N], rt, v[N], ans1; vector< pi > e[N]; double sum, sd, d[N], ans2 = 1e20; void dfs(int x, int f, int S) { s[x] = 1; int o = 0; for (ui i = 0; i < e[x].size(); i++) { int y = e[x][i].fi; if (v[y] || y == f) continue; dfs(y, x, S), s[x] += s[y], o = max(o, s[y]); } o = max(o, S - s[x]); if (o <= (S >> 1)) rt = x; } void calc(int x, int f, int o, int z) { sum += pow(z, 1.5) * w[x], d[o] += pow(z, 0.5) * 1.5 * w[x]; for (ui i = 0; i < e[x].size(); i++) { int y = e[x][i].fi; if (y == f) continue; calc(y, x, o, z + e[x][i].se); } } void dfs(int x, int S) { dfs(x, 0, S), x = rt, dfs(x, 0, S); if (v[x]) return; v[x] = 1, sum = sd = 0; for (ui i = 0; i < e[x].size(); i++) { int y = e[x][i].fi; d[y] = 0, calc(y, x, y, e[x][i].se), sd += d[y]; } if (sum < ans2) ans1 = x, ans2 = sum; for (ui i = 0; i < e[x].size(); i++) { int y = e[x][i].fi; if (sd - d[y] * 2 >= 0) continue; dfs(y, s[y]); break; } } int main() { rd(n); for (int i = 1; i <= n; i++) rd(w[i]); for (int i = 1, x, y, z; i < n; i++) rd(x), rd(y), rd(z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z)); dfs(1, n); printf("%d %.10f\n", ans1, ans2); return 0; } ```