CF566C Logistical Questions 题解
Visits: 422
题意
- 一棵 $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)$。
代码
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;
}