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