CF566C

求导的思想找极值点挺不错的，还有点分治降低树的高度。

1. 题意

题目传送门 Luogu

题目传送门 Codeforces

求有点权、边的长度的树的重心，距离定义为 $(\sum w{)}^{\frac{3}{2}}$，注意要求落在点上，并且求出该点到其他点的距离和。

$n\le 2\times {10}^5$。

2. 题解

首先，暴力 $O(n^2)$ 可以 TLE。

假设距离和函数为 $f(x)=\sum _{i=1}^{n}d(i,x{)}^{\frac{3}{2}}$。

我们考虑假设退化成一条链的情况：这个一定是一个下凸函数，我们可以直接三分答案，每一次求 $f(x)$ 为 $O(n)$ 的，总复杂度为 $O(n\log n)$。

可不可以不用三分呢？

观察到这个函数是一个多项式，我们可以对其求导。

最开始，这个导函数一直是负，突然到了最优解 $u$ 附近的时候，边为了正，很明显，我们可以先得到导函数，再对导函数二分查找第一次变为正的位置。

但是我们来到树上的时候，不能一步跳很远，只能单步跳，时间复杂度明显和高度 $h$ 有关，为 $O(nh)$，怎么办呢？

相信你已经想到了，直接点分治重构树！

我们看一下哪棵子树的导函数是小于 0 的，有小于 0 的向那边跳就是了。

同时有前面的理论，我们可以发现，树的重心一定只有一个（可能不在点上而在边上），他向四周扩散都是变大的。

我们层层逼近，一定只有 $\log n$ 层，时间复杂度为 $O(n\log n)$，可以通过。

总结：求导逼近极值点；点分治降低树高度。

void dfs(int x, int fa, double &dev, int nowd)
{
	// if (vis[x]) return;
	sum += pow(nowd, 1.5) * a[x], dev += 1.5 * sqrt(nowd) * a[x];
	for (int i = h[x]; ~i; i = ne[i])
		if (e[i] != fa) dfs(e[i], x, dev, nowd + w[i]);
}
 
void work(int x)
{
	if (vis[x]) return;
	get_wc(x, -1, get_size(x, -1), x);//求重心
	vis[x] = 1;
	sum = 0;
	double sumd = 0;
	for (int i = h[x]; ~i; i = ne[i])
	{
		dv[e[i]] = 0, dfs(e[i], x, dv[e[i]], w[i]), sumd += dv[e[i]];//求导数
	}
	if (sum < res) res = sum, ansu = x;
	for (int i = h[x]; ~i; i = ne[i])
	{
		if (sumd - 2 * dv[e[i]] <= 0){//这里是一步推导，我们如果向这边的话，其他的导数为正，这个为负，也就是总和减去两倍当前的导数
			work(e[i]);
			continue;
		}
	}
}