【Codeforces 566C】Logistical Questions | Mrsrz's blog

点分治。

题目大意：

给定一棵树，带点权和边权。令 $\mathrm{dist}(u,v)$ 表示树上点 $u$ 和 $v$ 之间的边权和。要求找到点 $s$，并最小化下面的式子的值。

$$\sum_{i=1}^n w_i\times \mathrm{dist}(s,i)\sqrt{\mathrm{dist}(s,i)}$$

题解：

考虑一条链的情况。这种情况我们可以把点放到坐标轴上，其距离就是坐标的差。

函数 $f(x)=c\cdot|x-x_0|^{1.5}$ 是下凸函数。而凸函数的和函数仍是凸函数。

因此和函数 $F(x)=\sum_{i=1}^n f_i(x)$ 也是凸函数。求其最值，我们可以用求导二分零点的方法。

---

考虑在树上的情况。

我们对每条边考虑，对于重心在这条边上的任意情况，其和函数都和链上的情况一样，仍是凸函数。因此最优的答案的重心是唯一的。

考虑在树上找这个重心，每次通过对每条边考虑，求出能使答案变小的方向继续找。

树上的问题可以使用点分治，判断往哪个方向走，就对每条边的和函数求导，往导数为负的方向走即可。

这里每次求导可以通过 $O(n)$ 的 dfs 处理出全部信息来完成。

时间复杂度 $O(n\log n)$。

Code：

#include<cstdio>
#include<cmath>
const int N=2e5+6;
int n,w[N],head[N],cnt,anf,rt,mxd[N],sz[N],all;
bool vis[N];
double ans=1e19,ds,D[N],res;
struct edge{
    int to,nxt,dis;
}e[N<<1];
void getrt(int now,int pre){
    sz[now]=1,mxd[now]=0;
    for(int i=head[now];i;i=e[i].nxt)
    if(!vis[e[i].to]&&pre!=e[i].to){
        getrt(e[i].to,now);
        if(mxd[now]<sz[e[i].to])mxd[now]=sz[e[i].to];
        sz[now]+=sz[e[i].to];
    }
    if(mxd[now]<all-sz[now])mxd[now]=all-sz[now];
    if(!rt||mxd[rt]>mxd[now])rt=now;
}
void dfs(int now,int pre,double&D,int dist){
    const double sq=sqrt(dist);
    res+=sq*dist*w[now],D+=sq*w[now],ds+=sq*w[now];
    for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=pre)
    dfs(e[i].to,now,D,dist+e[i].dis);
}
void solve(int now){
    vis[now]=1;
    ds=res=0;
    for(int i=head[now];i;i=e[i].nxt){
        D[e[i].to]=0;
        dfs(e[i].to,now,D[e[i].to],e[i].dis);
    }
    if(ans>res)ans=res,anf=now;
    for(int i=head[now];i;i=e[i].nxt)
    if(ds-2*D[e[i].to]<0){
        if(vis[e[i].to])break;
        all=sz[e[i].to]<sz[now]?sz[e[i].to]:all-sz[now];
        rt=0;
        getrt(e[i].to,now);
        solve(rt);
        break;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",w+i);
    for(int i=1;i<n;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
        e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
    }
    all=n;
    rt=0;
    getrt(1,0);
    solve(rt);
    printf("%d %.10e\n",anf,ans);
    return 0;
}