Description
给定一棵 nnn 个点的树 TTT,点有点权 aia_iai,边有边权 www.
定义 dist(u,v)\operatorname{dist}(u,v)dist(u,v) 为 u→vu\to vu→v 的简单路径上的边权和.
找到一个节点 uuu,使得 W=∑i=1ndist(u,i)32×aiW=\sum\limits_{i=1}^n \operatorname{dist}(u,i)^{\frac{3}{2}}\times a_iW=i=1∑ndist(u,i)23×ai 最小.
输出 uuu 和 WWW,若有多个 uuu,输出任意一个.
Limitations
1≤n≤2×1051\le n\le 2\times 10^51≤n≤2×105
1≤ai≤108,1≤w≤10001\le a_i\le 10^8,1\le w\le 10001≤ai≤108,1≤w≤1000
Solution
由于带 32\frac{3}{2}23 次方,不能按照一般方法处理.
注意到离真正答案(可能是边上的一点)越近,WWW 越小.
假设当前节点为 uuu,考虑向 u→vu\to vu→v 这条边移动 xxx 单位距离,则
W=(∑i∈son(u)ai×(dist(u,i)−x)32)+(∑i∉son(u)ai×(dist(u,i)+x)32)W=(\sum_{i\in \operatorname{son}(u)} a_i\times (\operatorname{dist}(u,i)-x)^{\frac{3}{2}})+(\sum_{i\notin \operatorname{son}(u)} a_i\times (\operatorname{dist}(u,i)+x)^{\frac{3}{2}})W=(i∈son(u)∑ai×(dist(u,i)−x)23)+(i∈/son(u)∑ai×(dist(u,i)+x)23)
对它求导:
W′=−(∑i∈son(u)ai×(dist(u,i)−x)12)+(∑i∉son(u)ai×(dist(u,i)+x)12)W^\prime=-(\sum_{i\in \operatorname{son}(u)} a_i\times (\operatorname{dist}(u,i)-x)^{\frac{1}{2}})+(\sum_{i\notin \operatorname{son}(u)} a_i\times (\operatorname{dist}(u,i)+x)^{\frac{1}{2}})W′=−(i∈son(u)∑ai×(dist(u,i)−x)21)+(i∈/son(u)∑ai×(dist(u,i)+x)21)
视 x→0x\to 0x→0,则 WWW 的瞬时变化量为:
−2(∑i∈son(u)ai×dist(u,i)12)+(∑i=1nai×dist(u,i)12)-2(\sum_{i\in \operatorname{son}(u)} a_i\times \operatorname{dist}(u,i)^{\frac{1}{2}})+(\sum_{i=1}^n a_i\times \operatorname{dist}(u,i)^{\frac{1}{2}})−2(i∈son(u)∑ai×dist(u,i)21)+(i=1∑nai×dist(u,i)21)
由 WWW 的下凸性,若第一个 i=vi=vi=v 时上述式子 <0<0<0,则 vvv 更优,向 vvv 走.
然而直接做是 O(n2)O(n^2)O(n2) 的,用点分治,从全树的中心出发(不带权),每次选择 vvv 后跳到 vvv 的子树中心,即可优化到 O(nlogn)O(n\log n)O(nlogn).
Code
2.24KB,515ms,40MB (c++23, msys2, O2)2.24\text{KB},515\text{ms},40\text{MB}\;\texttt{(c++23, msys2, O2)}2.24KB,515ms,40MB(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;
}