\[\]
CF566C Logistical Questions
Problem
给定一棵 \(n\) 个点的树，点权 \(w_i\)，边权 \(l_i\)。求点 \(p\)，使 \(\sum \operatorname{dist}^{\frac 32}(i, p)\cdot w_i\) 最小。
\(1 \le n \le 2 \times 10^5\)，\(0 \le w_i \le 10^8\)，\(1 \le l_i \le 1000\)。
Sol
hint：\(\left(d^{\frac 32}\right)'\) 单调递增。
类似于 快递员 的 trick？
考虑对于一个点 \(u\)，对于相邻点 \(v_{1..c}\)，尝试走一点来判断是否更优。不难证明，若 \(u \to v_k\) 最优，重心一定向 \(v_k\) 移动。于是以 \(u\) 为根进行一次 DFS，求出 \(\sum w\cdot d^{\frac 12}\) 后，对每条 \((u, v_{i})\) 边看看能不能走即可。
这里可能会有一点问题，因为可能这条边左右的点数不同。本来是 \(L' > R'\)，这条边走到一半变成 \(L'<R'\) 了，因此不能确定最优位置。但是由于最优位置输出的是点，这两个点都算一遍就行了。
但是可能会移动很多次。点分治即可。时间复杂度：\(O(n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb emplace_back
const int N = 2e5 + 10;
int n, R;
int a[N];
double f[N];
pair<double, int> ans;
pair<double, int> operator+(pair<double, int> a, pair<double, int> b) { return a.fi < b.fi ? a : b; }
vector<pii> e[N];
int mx[N], sz[N], vis[N];
void FindRoot(int u, int ff, int num) {mx[u] = 0, sz[u] = 1;for (auto [v, w] : e[u]) {if (vis[v] || v == ff) continue;FindRoot(v, u, num);sz[u] += sz[v];mx[u] = max(mx[u], sz[v]);}mx[u] = max(mx[u], num - sz[u]);if (mx[R] > mx[u]) R = u;
}
void DFS(int u, int ff, int d) {f[u] = a[u] * sqrt(d);for (auto [v, w] : e[u]) {if (v == ff) continue;DFS(v, u, d + w);f[u] += f[v];}
}
double GetDist(int u, int ff, int d) {double res = a[u] * pow(d, 1.5);for (auto [v, w] : e[u]) {if (v == ff) continue;res += GetDist(v, u, d + w);}return res;
}
void Divide(int u) {ans = ans + make_pair(GetDist(u, 0, 0), u);vis[u] = 1;DFS(u, 0, 0);int p = -1;double nd = 0;for (auto [v, w] : e[u])if (!vis[v] && f[v] > nd)nd = f[v], p = v;if (p == -1) return;R = 0, FindRoot(p, u, sz[p]);Divide(R);
}
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &a[i]);for (int i = 1, a, b, l; i < n; i++) {scanf("%d%d%d", &a, &b, &l);e[a].pb(b, l);e[b].pb(a, l);}ans = { GetDist(1, 0, 0), 1 };mx[0] = n + 1, R = 0, FindRoot(1, 0, n), Divide(R);printf("%d %.8lf\n", ans.se, ans.fi);return 0;
}