「VK Cup 2015 - Finals」A. Logistical Questions

Problem

Description

给定一棵 n 个点的树,点 u 有点权 w_{u} ,树边带权。
定义 f\left(u, v\right) = \operatorname{dis}\left(u, v\right)^{\frac{3}{2}}, \displaystyle{g(u) = \sum_{v = 1}^{n} w_{v} f\left(u, v\right)}
\underset{1 \le u \le n}{\arg \min} g(u) \displaystyle{\min_{1 \le u \le n} g(u)}

Constraints

1 \le n \le 2 \times 10^{5}, 0 \le w_{u} \le 10^{8}, 1 \le l_{i} \le 10^{3}

Solution

Analysis

对于任意一条路径 \left(u_{1}, u_{2}, \dots, u_{m}\right) 与任意点 p ,容易知道 h(x) = f\left(p, u_{x}\right) \left(x \in \left[1, m\right]\right) Convex function
由 Convex function 的性质可知 h(x) = w_{p} f\left(p, u_{x}\right) h(x) = \displaystyle{\sum_{p = 1}^{n} w_{p} f\left(p, u_{x}\right)} = g\left(u_{x}\right) 均为 Convex function。
由这个性质可以发现:对于一个点 u 及所有与 u 相邻的点 v ,至多只有一个 v 满足 g(v) < g(u)
因为若存在 u 及两个与其相邻的点 v_{1}, v_{2} ,满足 g\left(v_{1}\right) < g(u), g\left(v_{2}\right) < g(u) ,则路径 \left(v_{1}, u, v_{2}\right) 不满足上述性质。
那么这个问题如果放在序列(路径)上,直接二分就可以了;相应地,树上的问题就可以用树上的二分也就是点分治来解决。
找满足 g(v) < g(u) v 时,对 g 求导得到每个 v 相对于 u 的变化量,找到变化量小于 0 的那个 v 即可。

时间复杂度 O(n \log{n})

Code

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <bitset>
#include <cmath>

using i64 = long long;

constexpr int maxn = 200000;
constexpr int inf = 2147483647;

template <typename _Tp>
inline void chkMax(_Tp &x, const _Tp &y) {
(x < y) && (x = y);
}
template <typename _Tp>
inline bool bchkMin(_Tp &x, const _Tp &y) {
return (x > y) && (x = y, true);
}

namespace IOManager {
constexpr int FILESZ = 131072;
char buf[FILESZ];
const char *ibuf = buf, *tbuf = buf;

struct IOManager {
inline char gc() {
return (ibuf == tbuf) && (tbuf = (ibuf = buf) + fread(buf, 1, FILESZ, stdin), ibuf == tbuf) ? EOF : *ibuf++;
}

template <typename _Tp>
inline operator _Tp() {
_Tp s = 0u; char c = gc();
for (; c < 48; c = gc());
for (; c > 47; c = gc())
s = (_Tp)(s * 10u + c - 48u);
return s;
}
};
} IOManager::IOManager io;

struct Edge {
int v, w; Edge *las;
inline Edge* init(const int &to, const int &val, Edge *const &ls) {
return v = to, w = val, las = ls, this;
}
} *las[maxn + 1];

inline void lnk() {
static Edge pool[maxn << 1], *alc = pool - 1;
const int u = io, v = io, w = io;
las[u] = (++alc)->init(v, w, las[u]);
las[v] = (++alc)->init(u, w, las[v]);
}

int w[maxn + 1],
sz[maxn + 1],
totalsz, mxsz, root;
std::bitset<maxn + 1> vis;

void precalc(const int &u, const int &fa) {
sz[u] = 1;
for (Edge *o = las[u]; o; o = o->las)
if (!vis[o->v] && o->v != fa) {
precalc(o->v, u);
sz[u] += sz[o->v];
}

int mx = totalsz - sz[u];
for (Edge *o = las[u]; o; o = o->las)
if (!vis[o->v] && o->v != fa)
chkMax(mx, sz[o->v]);
if (bchkMin(mxsz, mx)) root = u;
}

int src, dep;
double sum, dsum, d[maxn + 1];
void calc(const int &u, const int &fa) {
const double sqrtdep = sqrt((double)dep);
sum += dep * sqrtdep * w[u];
d[src] += 1.5 * sqrtdep * w[u];
for (Edge *o = las[u]; o; o = o->las)
if (o->v != fa)
dep += o->w,
calc(o->v, u),
dep -= o->w;
}

int pos; double minsum;
void calc(const int &u) {
if (vis[u]) return;
vis[u] = true;

sum = dsum = 0;
for (Edge *o = las[u]; o; o = o->las)
d[o->v] = 0, src = o->v, dep = o->w,
calc(o->v, u), dsum += d[o->v];

if (bchkMin(minsum, sum)) pos = u;

for (Edge *o = las[u]; o; o = o->las)
if (dsum < d[o->v] + d[o->v]) {
totalsz = sz[o->v]; mxsz = inf;
precalc(o->v, 0);
return calc(root);
}
}

int main() {
const int n = io;
for (int i = 1; i <= n; ++i) w[i] = io;
for (int i = n - 1; i != 0; --i) lnk();

minsum = 1e20;
totalsz = n; mxsz = inf;
precalc(1, 0); precalc(root, 0);
calc(root);

printf("%d %.15lf", pos, minsum);

return 0;
}