CF566C A Logistical Questions

考虑当前在 $u$ ,如何确定带权重心在哪个子树中。考虑往某个子树移动一个微小距离,那么所有点到这个点距离的变化是

如果这个东西大于 $0$ ,就意味着往这个点移是优的,也就是

如果我们设 $f(x) = x^{1.5}$ ,那么就是

我们点分治一下,这样就只需要跳 $\log n$ 次了。

可能还需要证明一下能取到最小值的位置只有 $1$ 个位置,因为 $f(x)$ 是凸函数,所以只有一个点能取到最优的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "assert.h"
#include "cmath"
using namespace std;
#define MAXN 200006
int n;
int A[MAXN];
int head[MAXN] , to[MAXN << 1] , nex[MAXN << 1] , wto[MAXN << 1] , ecn;
void ade( int u , int v , int w ) {
wto[++ ecn] = w , to[ecn] = v , nex[ecn] = head[u] , head[u] = ecn;
}
int vis[MAXN] , siz[MAXN] , sz;
int p , mx;
void dfs( int u , int fa ) {
siz[u] = 1;
int s = 0;
for( int i = head[u] ; i ; i = nex[i] ) {
int v = to[i];
if( v == fa || vis[v] ) continue;
dfs( v , u );
siz[u] += siz[v];
s = max( s , siz[v] );
}
s = max( s , sz - siz[u] );
if( s < mx ) p = u , mx = s;
}
int dep[MAXN]; double all , pia;
int via = 0 , pre;
double getit( int u , int fa ) {
if( u == pre ) via = 1;
double ret = A[u] * 1.5 * sqrt( 1.0 * dep[u] );
all += A[u] * sqrt( 1.0 * dep[u] ) * dep[u];
pia += ret;
for( int i = head[u] ; i ; i = nex[i] ) {
int v = to[i];
if( v == fa ) continue;
dep[v] = dep[u] + wto[i];
ret += getit( v , u );
}
return ret;
}
double re[MAXN];
double ans = 8e18; int ps;
void solve( int u ) {
// cout << u << endl;
vis[u] = 1;
all = pia = 0.0;
int tr = u;
for( int i = head[u] ; i ; i = nex[i] ) {
int v = to[i];
dep[v] = wto[i];
re[v] = getit( v , u );
if( via ) tr = v;
}
if( all < ans ) ans = all , ps = u;
for( int i = head[u] ; i ; i = nex[i] ) {
int v = to[i];
if( vis[v] ) continue;
if( pia - 2 * re[v] <= 1e-7 ) {
p = 0 , mx = 0x3f3f3f3f;
sz = siz[u];
dfs( v , u );
pre = u;
solve( p );
dep[tr] = 0.0;
all = 0;
getit( tr , tr );
if( all < ans ) ans = all , ps = tr;
}
}
}
int main() {
cin >> n;
for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]);
for( int i = 1 , u , v , w ; i < n ; ++ i ) {
scanf("%d%d%d",&u,&v,&w) , ade( u , v , w ) , ade( v , u , w );
}
mx = 0x3f3f3f3f;
sz = n;
dfs( 1 , 1 );
solve( p );
printf("%d %.7lf",ps,ans);
}
文章作者: yijan
文章链接: https://yijan.co/2021/02/13/cf566c-a-logistical-questions/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog