题解 CF566C 【Logistical Questions】

· · 题解

CF566C Logistical Questions

题意

题解

设 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;
}