Description

给定一棵 $n$ 个点的树 $T$，点有点权 $a_i$，边有边权 $w$.
定义 $\mathrm{dist}(u,v)$ 为 $u\to v$ 的简单路径上的边权和.
找到一个节点 $u$，使得 $W=\sum _{i=1}^n\mathrm{dist}(u,i{)}^{\frac{3}{2}}\times a_i$ 最小.
输出 $u$ 和 $W$，若有多个 $u$，输出任意一个.

Limitations

$1\le n\le 2\times 10^5$
$1\le a_i\le 10^8,1\le w\le 1000$

Solution

由于带 $\frac{3}{2}$ 次方，不能按照一般方法处理.
注意到离真正答案（可能是边上的一点）越近，$W$ 越小.
假设当前节点为 $u$，考虑向 $u\to v$ 这条边移动 $x$ 单位距离，则
$$W=(\sum _{i\in \mathrm{son}(u)}{a}_i\times (\mathrm{dist}(u,i)-x{)}^{\frac{3}{2}})+(\sum _{i\notin \mathrm{son}(u)}{a}_i\times (\mathrm{dist}(u,i)+x{)}^{\frac{3}{2}})$$

对它求导：
$$W^{\prime }=-(\sum _{i\in \mathrm{son}(u)}{a}_i\times (\mathrm{dist}(u,i)-x{)}^{\frac{1}{2}})+(\sum _{i\notin \mathrm{son}(u)}{a}_i\times (\mathrm{dist}(u,i)+x{)}^{\frac{1}{2}})$$

视 $x\to 0$，则 $W$ 的瞬时变化量为：
$$-2(\sum _{i\in \mathrm{son}(u)}{a}_i\times \mathrm{dist}(u,i{)}^{\frac{1}{2}})+(\sum _{i=1}^n{a}_i\times \mathrm{dist}(u,i{)}^{\frac{1}{2}})$$

由 $W$ 的下凸性，若第一个 $i=v$ 时上述式子 $<0$，则 $v$ 更优，向 $v$ 走.
然而直接做是 $O(n^2)$ 的，用点分治，从全树的中心出发（不带权），每次选择 $v$ 后跳到 $v$ 的子树中心，即可优化到 $O(n\log n)$.

Code

$2.24\text{KB},515\text{ms},40\text{MB}\text{(c++23, msys2, O2)}$

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}constexpr f8 inf = 1e20;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) cin >> a[i];vector<vector<pair<int, int>>> g(n);for (int i = 0, u, v, w; i < n - 1; i++) {cin >> u >> v >> w, u--, v--;g[u].emplace_back(v, w);g[v].emplace_back(u, w);}vector<int> siz(n), cur(n);vector<bool> vis(n);int rt = -1;auto findroot = [&](auto&& self, int u, int fa, int sum) -> void {siz[u] = 1, cur[u] = 0;for (auto [v, w] : g[u]) {if (v == fa || vis[v]) continue;self(self, v, u, sum);siz[u] += siz[v];chmax(cur[u], siz[v]);}chmax(cur[u], sum - siz[u]);if (rt == -1 || cur[u] < cur[rt]) rt = u;};f8 s1, s2;vector<f8> dp(n);auto getdis = [&](auto&& self, int u, int fa, int top, i64 dis) -> void {s1 += a[u] * dis * sqrtl(dis); s2 += a[u] * sqrtl(dis) * 3 / 2;dp[top] += a[u] * sqrtl(dis) * 3 / 2;for (auto [v, w] : g[u]) {if (v == fa) continue;self(self, v, u, top, dis + w);}};pair<int, f8> res{-1, inf};auto solve = [&](auto&& self, int u) -> void {if (vis[u]) return;vis[u] = true;s1 = s2 = 0;for (auto [v, w] : g[u]) {dp[v] = 0;getdis(getdis, v, u, v, w);}if (s1 < res.second) res = {u, s1};for (auto [v, w] : g[u])if (s2 - dp[v] * 2 < 0) {rt = -1;findroot(findroot, v, u, siz[v]); self(self, rt); break;}};findroot(findroot, 0, -1, n);solve(solve, rt);printf("%d %.10lf\n", res.first + 1, res.second);return 0;
}