求导的思想找极值点挺不错的,还有点分治降低树的高度。
1. 题意
题目传送门 Luogu
题目传送门 Codeforces
求有点权、边的长度的树的重心,距离定义为 ,注意要求落在点上,并且求出该点到其他点的距离和。
。
2. 题解
首先,暴力 可以 TLE。
假设距离和函数为 。
我们考虑假设退化成一条链的情况:这个一定是一个下凸函数,我们可以直接三分答案,每一次求 为 的,总复杂度为 。
可不可以不用三分呢?
观察到这个函数是一个多项式,我们可以对其求导。
最开始,这个导函数一直是负,突然到了最优解 附近的时候,边为了正,很明显,我们可以先得到导函数,再对导函数二分查找第一次变为正的位置。
但是我们来到树上的时候,不能一步跳很远,只能单步跳,时间复杂度明显和高度 有关,为 ,怎么办呢?
相信你已经想到了,直接点分治重构树!
我们看一下哪棵子树的导函数是小于 0 的,有小于 0 的向那边跳就是了。
同时有前面的理论,我们可以发现,树的重心一定只有一个(可能不在点上而在边上),他向四周扩散都是变大的。
我们层层逼近,一定只有 层,时间复杂度为 ,可以通过。
总结:求导逼近极值点;点分治降低树高度。
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
| void dfs(int x, int fa, double &dev, int nowd) { 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; } } }
|
Related Issues not found
Please contact @mydcwfy to initialize the comment