「VK Cup 2015 - Finals」A. Logistical Questions

Posted on | Edited on | In , ,

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