CF566C Logistical Questions

IOI2020集训队作业

唉...我以后中午睡不上20min就石祥吧

真的非常好用,能得到50min高效率加成

一棵 $n$ 个节点的树，点有点权，边有边权。
两点间的距离定义为两点间边权和的 $\frac 32$ 次方。
求这棵树的带权重心。
$n \le 2 \times 10^5$ 。

考虑难在哪,因为我们不能直接枚举每个点算答案,而且要想得到一个点的答案必须暴力O(n)才行/惊恐

因为查询一个点做根他给出一个2/3次方我们啥数据结构都维护不了啊

所以我们考虑怎么实现一种检验次数最少的方法....?先发现了这个函数是凸函数

也就是说我们最优点只有一个,因为如果有多个,这个函数就不凸了啊,你可能会说是一条边两边的点都是最优的,这样我们可以认为这个边上有一个点是最优的啊,再加上题目中只要求输出一个方案,所以和之前是一样的

而且从这个点向左右移动答案一定会变大....也就是说我们从这个点向其他点走,导数....可以这么叫吧值会是正的

如果是一条链我们就二分了,现在我们是一棵树,就点分治

现在我们要找的就是这样一个点,他满足走向周围的点导数都为正

也就是我们对于任何一个点,每次朝着导数为负的那个点走去就行,因为是树所以肯定只有一个这样的点

求一个点x到他一个儿子导数??

设 $p_i$ 为x的一个儿子i子树内的导数值和

然后我们向i转移的导数为 $\sum{p_j}-2*p_i$ 找到这个小于0的即可

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int MAXN = 1e6 + 7;
int n, w[MAXN], s[MAXN], rt, vis[MAXN], ans1, ccnt;
int home[MAXN], to[MAXN], nxt[MAXN], len[MAXN];
double sum, sd, d[MAXN], ans2 = 1e20;

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x = 0, f = 1;
		register char s = 0;
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;

inline void ct(int x, int y, int z) {
	++ccnt;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	len[ccnt] = z;
}

void dfs(int x, int f, int S) {
	s[x] = 1;
	int o = 0;
	for(int i = home[x]; i; i = nxt[i]) {
		int v = to[i];
		if(v == f || vis[v])continue;
		dfs(v, x, S);
		s[x] += s[v];
		o = max(o, s[v]);
	}
	o = max(o, S - s[x]);
	if(o <= (S >> 1))rt = x;
}

inline void calc(int x, int f, int o, int z) {
	sum += pow(z, 1.5) * w[x], d[o] += pow(z, 0.5) * 1.5 * w[x];
	for(int i = home[x]; i; i = nxt[i]) {
		int v = to[i];
		if(v == f)continue;
		calc(v, x, o, z + len[i]);
	}
}

inline void dfs(int x, int S) {
	dfs(x, 0, S);
	x = rt;
	dfs(x, 0, S);
	if(vis[x])return ;
	vis[x] = 1;
	sum = sd = 0;
	for(int i = home[x]; i; i = nxt[i]) {
		int v = to[i];
		d[v] = 0;
		calc(v, x, v, len[i]), sd += d[v];
	}
	if(sum < ans2)ans1 = x, ans2 = sum;
	for(int i = home[x]; i; i = nxt[i]) {
		int v = to[i];
		if(sd - d[v] * 2 >= 0)continue;
		dfs(v, s[v]);
		break;
	}

}

int main() {
	//freopen("test.in","r",stdin);
	n = read();
	for(int i = 1; i <= n; ++i)w[i] = read();
	for(int i = 1, x, y, z; i < n; ++i) {
		x = read();
		y = read();
		z = read();
		ct(x, y, z);
		ct(y, x, z);
	}
	dfs(1, n);
	printf("%d %.10f\n", ans1, ans2);
	return 0;
}

夏晓光(loveJY)的博客

CF559E Gerald and Path