CF566C Logistical Questions Solution

发布于:2025-08-16 ⋅ 阅读:(22) ⋅ 点赞:(0)

Description

给定一棵 nnn 个点的树 TTT,点有点权 aia_iai,边有边权 www.
定义 dist⁡(u,v)\operatorname{dist}(u,v)dist(u,v)u→vu\to vuv 的简单路径上的边权和.
找到一个节点 uuu,使得 W=∑i=1ndist⁡(u,i)32×aiW=\sum\limits_{i=1}^n \operatorname{dist}(u,i)^{\frac{3}{2}}\times a_iW=i=1ndist(u,i)23×ai 最小.
输出 uuuWWW,若有多个 uuu,输出任意一个.

Limitations

1≤n≤2×1051\le n\le 2\times 10^51n2×105
1≤ai≤108,1≤w≤10001\le a_i\le 10^8,1\le w\le 10001ai108,1w1000

Solution

由于带 32\frac{3}{2}23 次方,不能按照一般方法处理.
注意到离真正答案(可能是边上的一点)越近,WWW 越小.
假设当前节点为 uuu,考虑向 u→vu\to vuv 这条边移动 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=(ison(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=(ison(u)ai×(dist(u,i)x)21)+(i/son(u)ai×(dist(u,i)+x)21)

x→0x\to 0x0,则 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(ison(u)ai×dist(u,i)21)+(i=1nai×dist(u,i)21)

WWW 的下凸性,若第一个 i=vi=vi=v 时上述式子 <0<0<0,则 vvv 更优,向 vvv 走.
然而直接做是 O(n2)O(n^2)O(n2) 的,用点分治,从全树的中心出发(不带权),每次选择 vvv 后跳到 vvv 的子树中心,即可优化到 O(nlog⁡n)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;
}

网站公告

今日签到

点亮在社区的每一天
去签到