Visits: 358

CF566C Logistical Questions

题意

• 一棵 $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;
}